Improved algorithms for maximum agreement and compatible supertrees

DOI10.1007/s00453-009-9303-6zbMath1209.68373MaRDI QIDQ627540

Viet Tung Hoang, Wing-Kin Sung

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9303-6

zbMATH Keywords

phylogenetic tree; maximum agreement supertree; maximum compatible supertree; suptree

Mathematics Subject Classification ID

92D15: Problems related to evolution

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Fixed-Parameter Algorithms for Finding Agreement Supertrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rooted maximum agreement supertrees
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• The complexity of reconstructing trees from qualitative characters and subtrees
• Kaikoura tree theorems: Computing the maximum agreement subtree
• On the agreement of many trees
• A supertree method for rooted trees
• An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
• An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
• Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
• Tree Contractions and Evolutionary Trees
• Sparse Dynamic Programming for Evolutionary-Tree Comparison
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time
• Combinatorial Pattern Matching
• On the complexity of comparing evolutionary trees