TY - JOUR
T1 - An O(n log n) algorithm for the maximum agreement subtree problem for binary trees
AU - Cole, Richard
AU - Farach-Colton, Martin
AU - Hariharan, Ramesh
AU - Przytycka, Teresa
AU - Thorup, Mikkel
PY - 2000
Y1 - 2000
N2 - 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(n log n) time algorithm for this problem.
AB - 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(n log n) time algorithm for this problem.
KW - Agreement subtree
KW - Algorithms
UR - http://www.scopus.com/inward/record.url?scp=0035189546&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035189546&partnerID=8YFLogxK
U2 - 10.1137/S0097539796313477
DO - 10.1137/S0097539796313477
M3 - Article
AN - SCOPUS:0035189546
SN - 0097-5397
VL - 30
SP - 1385
EP - 1404
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 5
ER -