polytree (568B)
1 # Polytree 2 3 https://en.wikipedia.org/wiki/Polytree 4 5 A polytree is a [directed_acyclic_graph] whose underlying [undirected_graph] is a [tree] 6 7 A polytree is always a [multitree] 8 9 In a polytree, we can do [transitive_closure] in [output_linear] time, and do [enumeration] of reachable leaves with linear preprocessing and constant delay 10 - this is like [boolean_matrix_multiplication] when there are no duplicate ways to obtain ones 11 - like [context_free_grammar_unambiguous] 12 - like [circuit] [deterministic] 13 14 Up: [graph_family] 15 16 See also: [multitree], [pseudoforest]