Cavity matchings, label compressions, and unrooted evolutionary trees

Ming Yang Kao*, Tak Wah Lam, Wing Kin Sung, Hing Fung Ting

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.5 log n) time for trees with unbounded degrees, matching the best known time complexity for the rooted case. Our algorithm allows the input trees to be mixed trees, i.e., trees that may contain directed and undirected edges at the same time. Our algorithm adopts a recursive strategy exploiting a technique called label compression. The backbone of this technique is an algorithm that computes the maximum weight matchings over many subgraphs of a bipartite graph as fast as it takes to compute a single matching.

Original languageEnglish (US)
Pages (from-to)602-624
Number of pages23
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2000


  • All-cavity maximum weight matchings
  • Computational biology
  • Evolutionary trees
  • Label compressions
  • Mixed trees
  • Unrooted trees

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Cavity matchings, label compressions, and unrooted evolutionary trees'. Together they form a unique fingerprint.

Cite this