An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (5) , 1385-1404
- https://doi.org/10.1137/s0097539796313477
Abstract
The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions of the two trees restricted to these items are isomorphic. We consider the case which occurs frequently in practice, i.e., the case when the trees are binary, and give an O(nlog n) time algorithm for this problem.Keywords
This publication has 10 references indexed in Scilit:
- Tree Contractions and Evolutionary TreesSIAM Journal on Computing, 1998
- Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient AlgorithmsSIAM Journal on Computing, 1997
- Sparse Dynamic Programming for Evolutionary-Tree ComparisonSIAM Journal on Computing, 1997
- Fast Comparison of Evolutionary TreesInformation and Computation, 1995
- On the agreement of many treesInformation Processing Letters, 1995
- An algorithm to find agreement subtreesJournal of Classification, 1995
- Kaikoura tree theorems: Computing the maximum agreement subtreeInformation Processing Letters, 1993
- Obtaining common pruned treesJournal of Classification, 1985
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- A Best Possible Bound for The Weighted Path Length of Binary Search TreesSIAM Journal on Computing, 1977