The asymmetric median tree. --- A new model for building consensus trees

DOI10.1016/S0166-218X(96)00071-6zbMath0868.92017OpenAlexW2091901265MaRDI QIDQ5961632

Tandy J. Warnow, Cynthia A. Phillips

Publication date: 11 August 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

approximation algorithmoptimization problemevolutionary treespolynomial-time algorithms\(k\)-colored graphsasymmetric median tree problemconsensus tree constructionmaximum independent set problemmeasure of phylogenetic resolution

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Complexity and performance of numerical algorithms (65Y20)

Related Items

Pareto quantiles of unlabeled tree objects ⋮ Tropical medians by transportation ⋮ DASACT: a decision aiding software for axiomatic consensus theory ⋮ Unnamed Item ⋮ When two trees go to war ⋮ Generalized median graphs and applications ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ Stackelberg Max Closure with Multiple Followers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal algorithms for comparing trees with labeled leaves
• N-trees as nestings: Complexity, similarity, and consensus
• When is one estimate of evolutionary relationships a refinement of another?
• An idealized concept of the true cladistic character
• A mathematical foundation for the analysis of cladistic character compatibility
• An algebraic analysis of cladistic characters
• Kaikoura tree theorems: Computing the maximum agreement subtree
• On the agreement of many trees
• The median procedure for n-trees
• Improved non-approximability results
• A Formal Theory of Consensus
• Tree Contractions and Evolutionary Trees
• Tree Compatibility and Inferring Evolutionary History
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Efficient algorithms for inferring evolutionary trees