A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees

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

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

21 Scopus citations

Abstract

Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n and W be the node count and the total weight of G. We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW) -time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G — {u} for all nodes u in O(W) time. As immediate applications of these algorithms, the best known time complexity of computing a maximum agreement subtree of two ℓ-leaf rooted or unrooted evolutionary trees is reduced from O(ℓ1.5 log ℓ) to O(l1.5).

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
EditorsJaroslav Nešetřil
PublisherSpringer Verlag
Pages438-449
Number of pages12
ISBN (Print)3540662510, 9783540662518
DOIs
StatePublished - Jan 1 1999
Event7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic
Duration: Jul 16 1999Jul 18 1999

Publication series

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

Other

Other7th Annual European Symposium on Algorithms, ESA 1999
CountryCzech Republic
CityPrague
Period7/16/997/18/99

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., Lam, T. W., Sung, W. K., & Ting, H. F. (1999). A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In J. Nešetřil (Ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings (pp. 438-449). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_38