A decomposition theorem for maximum weight bipartite matchings

Citation
My. Kao et al., A decomposition theorem for maximum weight bipartite matchings, SIAM J COMP, 31(1), 2001, pp. 18-26
Citations number
15
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
18 - 26
Database
ISI
SICI code
0097-5397(20010729)31:1<18:ADTFMW>2.0.ZU;2-S
Abstract
Let G be a bipartite graph with positive integer weights on the edges and w ithout isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k (x, y) be log x/log(x(2)/y). We pr esent a new decomposition theorem for maximum weight bipartite matchings an d use it to design an O (n rootW/k(n,W/N))-time algorithm for computing a m aximum weight matching of G. This algorithm bridges a long-standing gap bet ween 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 weigh t matching of G-{u} for all nodes u in O(W) time.