TY - GEN

T1 - Tree contractions and evolutionary trees

AU - Kao, Ming Yang

PY - 1997/1/1

Y1 - 1997/1/1

N2 - An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T1 and T2 with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log2 n) and is within a log n factor of optimal. For general d, this algorithm runs in O(nd 2 logd log2 n) time or alternatively in O(nd√d log3 n) time.

AB - An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T1 and T2 with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log2 n) and is within a log n factor of optimal. For general d, this algorithm runs in O(nd 2 logd log2 n) time or alternatively in O(nd√d log3 n) time.

UR - http://www.scopus.com/inward/record.url?scp=84957701728&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957701728&partnerID=8YFLogxK

U2 - 10.1007/3-540-62592-5_81

DO - 10.1007/3-540-62592-5_81

M3 - Conference contribution

AN - SCOPUS:84957701728

SN - 3540625925

SN - 9783540625926

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 299

EP - 310

BT - Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings

A2 - Bongiovanni, Giancarlo

A2 - Bovet, Daniel Pierre

A2 - Di Battista, Giuseppe

PB - Springer Verlag

T2 - 3rd Italian Conference on Algorithms and Complexity, CIAC 1997

Y2 - 12 March 1997 through 14 March 1997

ER -