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.