A supertree method for rooted trees
type: Item
instance of: scholarly article
title: A supertree method for rooted trees
zbMATH Open document ID: 0961.05015
DOI: 10.1016/S0166-218X(00)00202-X
author: Charles Semple
author: Mike Steel
published in: Discrete Applied Mathematics
publication date: 2001-05-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 92D15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1512452
zbMATH Keywords: rooted phylogenetic tree
zbMATH Keywords: supertree
zbMATH Keywords: consensus tree
Wikidata QID: Q56764978
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: N-trees as nestings: Complexity, similarity, and consensus
cites work: Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
cites work: Extension operations on sets of leaf-labelled trees
cites work: An efficient algorithm for supertrees
cites work: Multi-Terminal Network Flows
cites work: Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
cites work: Reconstruction of rooted trees from subtrees
cites work: The complexity of reconstructing trees from qualitative characters and subtrees
full work available at URL: s0166-218x(00)00202-x
OpenAlex ID: W2033854905
DBLP publication ID: journals/dam/SempleS00
Recommended article: An efficient algorithm for supertrees
Recommended article: Constructing rooted supertrees using distances
Recommended article: Extending the limits of supertree methods
Recommended article: Q4422502
Recommended article: Rooted maximum agreement supertrees
Recommended article: LATIN 2004: Theoretical Informatics
Recommended article: A Class of General Supertree Methods for Nested Taxa
Recommended article: Reconstruction of rooted trees from subtrees
description: scientific article; zbMATH DE number 1512452