A supertree method for rooted trees (Q1582076): Difference between revisions
From MaRDI portal
Latest revision as of 10:08, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A supertree method for rooted trees |
scientific article |
Statements
A supertree method for rooted trees (English)
0 references
21 May 2001
0 references
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.
0 references
rooted phylogenetic tree
0 references
supertree
0 references
consensus tree
0 references
0 references
0 references