Maximum agreement and compatible supertrees

DOI10.1016/j.jda.2006.08.005zbMath1129.05047OpenAlexW2106706740MaRDI QIDQ2466022

François Nicolas, Vincent Berry

Publication date: 11 January 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.08.005

zbMATH Keywords

algorithmstreescomputational biologysupertreesisomorphism and refinement relations

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Kernel and fast algorithm for dense triplet inconsistency ⋮ Building a small and informative phylogenetic supertree ⋮ Gene tree correction for reconciliation and species tree inference: complexity and algorithms ⋮ New results on optimizing rooted triplets consistency ⋮ Fixed-Parameter Algorithms for Finding Agreement Supertrees ⋮ On the Maximum Agreement Subtree Conjecture for Balanced Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rooted maximum agreement supertrees
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• On the complexity of constructing evolutionary trees
• Finding largest subtrees and smallest supertrees
• Phylogenetic supertrees. Combining information to reveal the tree of life
• Extension operations on sets of leaf-labelled trees
• Finding a maximum compatible tree is NP-hard for sequences and 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
• Approximating the domatic number
• Fast Algorithms for Finding Nearest Common Ancestors
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• 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
• Efficient probabilistically checkable proofs and applications to approximations
• Algorithms and Computation
• Computing and Combinatorics
• On the complexity of comparing evolutionary trees

This page was built for publication: Maximum agreement and compatible supertrees