Maximum agreement and compatible supertrees
From MaRDI portal
Publication:2466022
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
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