Improved algorithms for maximum agreement and compatible supertrees

DOI10.1007/s00453-009-9303-6zbMath1209.68373OpenAlexW2096160639MaRDI 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 treemaximum agreement supertreemaximum compatible supertreesuptree

Mathematics Subject Classification ID

Problems related to evolution (92D15) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

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

This page was built for publication: Improved algorithms for maximum agreement and compatible supertrees