Tree contractions and evolutionary trees

Ming Yang Kao*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings
EditorsGiancarlo Bongiovanni, Daniel Pierre Bovet, Giuseppe Di Battista
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540625925, 9783540625926
StatePublished - 1997
Event3rd Italian Conference on Algorithms and Complexity, CIAC 1997 - Rome, Italy
Duration: Mar 12 1997Mar 14 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Italian Conference on Algorithms and Complexity, CIAC 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Tree contractions and evolutionary trees'. Together they form a unique fingerprint.

Cite this