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

VL - 30

SP - 1385

EP - 1404

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 5

ER -