@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}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999. Copyright: Copyright 2016 Elsevier B.V., All rights reserved.; 7th Annual European Symposium on Algorithms, ESA 1999 ; Conference date: 16-07-1999 Through 18-07-1999",

year = "1999",

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{\v s}et{\v r}il",

booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",

}