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 Citations (Scopus)

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

Bipartite Matching
Evolutionary Tree
Decomposition Theorem
Decomposition
Computing
Time Complexity
Vertex of a graph
Bipartite Graph
Cardinality
Count
Leaves
Integer

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
Kao, Ming Yang ; Lam, Tak Wah ; Sung, Wing Kin ; Ting, Hing Fung. / A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. editor / Jaroslav Nešetřil. Springer Verlag, 1999. pp. 438-449 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{7ac203bcfc1647a5b1ea3f4dd7bf64d8,
title = "A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees",
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).",
author = "Kao, {Ming Yang} and Lam, {Tak Wah} and Sung, {Wing Kin} and Ting, {Hing Fung}",
year = "1999",
month = "1",
day = "1",
doi = "10.1007/3-540-48481-7_38",
language = "English (US)",
isbn = "3540662510",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "438--449",
editor = "Jaroslav Nešetřil",
booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",
address = "Germany",

}

Kao, MY, Lam, TW, Sung, WK & Ting, HF 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1643, Springer Verlag, pp. 438-449, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 7/16/99. https://doi.org/10.1007/3-540-48481-7_38

A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. / Kao, Ming Yang; Lam, Tak Wah; Sung, Wing Kin; Ting, Hing Fung.

Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. ed. / Jaroslav Nešetřil. Springer Verlag, 1999. p. 438-449 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643).

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

TY - GEN

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

AU - Kao, Ming Yang

AU - Lam, Tak Wah

AU - Sung, Wing Kin

AU - Ting, Hing Fung

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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).

AB - 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).

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

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

U2 - 10.1007/3-540-48481-7_38

DO - 10.1007/3-540-48481-7_38

M3 - Conference contribution

AN - SCOPUS:84958038951

SN - 3540662510

SN - 9783540662518

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

SP - 438

EP - 449

BT - Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings

A2 - Nešetřil, Jaroslav

PB - Springer Verlag

ER -

Kao MY, Lam TW, Sung WK, Ting HF. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Nešetřil J, editor, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Springer Verlag. 1999. p. 438-449. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-48481-7_38