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

9 Scopus citations

Abstract

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
Volume30
Issue number2
DOIs
StatePublished - 2000

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

Cite this