A supertree method for rooted trees (Q1582076): Difference between revisions

Denote \(T_1, T_2, \ldots, T_k\) a bunch of trees. A tree \(T\) is a compatible supertree of them, if each \(T_i\) can be derived from \(T\) as topological subtree, induced by leaves. This paper describes a polynomial time algorithm to derive a compatible supertree from a bunch of leaf labelled rooted trees (phylogenies), if it exists. (Recently it was proved that there is no ``reasonable'' supertree algorithm if the subtrees are unrooted.) Its \texttt{MinCutSupertree} algorithm is symmetric in the sense that its result does not depend on the order or on the labelling of the input trees, and it can be naturally extended to weighted input trees. The method is a modification of the algorithm of Aho et al.