Kaikoura tree theorems: Computing the maximum agreement subtree

DOI10.1016/0020-0190(93)90181-8zbMath0942.68578OpenAlexW1963749031MaRDI QIDQ1313765

Mike A. Steel, Tandy J. Warnow

Publication date: 14 August 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90181-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD ⋮ The agreement metric for labeled binary trees ⋮ Bounds on the Expected Size of the Maximum Agreement Subtree ⋮ Computing the unrooted maximum agreement subtree in sub-quadratic time ⋮ Generalized LCS ⋮ An \(O(n\log n)\)-time algorithm for the maximum constrained agreement subtree problem for binary trees ⋮ On the agreement of many trees ⋮ Finding a maximum compatible tree is NP-hard for sequences and trees ⋮ Inducibility in Binary Trees and Crossings in Random Tanglegrams ⋮ Computing the agreement of trees with bounded degrees ⋮ Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees ⋮ Improved algorithms for maximum agreement and compatible supertrees ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ On the extremal maximum agreement subtree problem ⋮ On the ancestral compatibility of two phylogenetic trees with nested taxa ⋮ The maximum agreement subtree problem ⋮ Analysis of the Period Recovery Error Bound ⋮ From constrained to unconstrained maximum agreement subtree in linear time ⋮ Computing the maximum agreement of phylogenetic networks ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ On the complexity of comparing evolutionary trees ⋮ The asymmetric median tree. --- A new model for building consensus trees ⋮ Approximate labelled subtree homeomorphism ⋮ Bounds on the Expected Size of the Maximum Agreement Subtree for a Given Tree Shape ⋮ Novel phylogenetic network distances based on cherry picking ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ An improved bound on the maximum agreement subtree problem ⋮ An improved algorithm for the maximum agreement subtree problem ⋮ On the Maximum Agreement Subtree Conjecture for Balanced Trees ⋮ TreeOfTrees method to evaluate the congruence between gene trees

Cites Work

• Unnamed Item
• An algorithm to find agreement subtrees
• Faster Scaling Algorithms for Network Problems