## Abstract

Let G be a bipartite graph with positive integer weights on the edges and without 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 present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW/k(n, W/N))-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.

Original language | English (US) |
---|---|

Pages (from-to) | 18-26 |

Number of pages | 9 |

Journal | SIAM Journal on Computing |

Volume | 31 |

Issue number | 1 |

DOIs | |

State | Published - 2001 |

## Keywords

- All-cavity matchings
- Graph algorithms
- Maximum weight matchings
- Minimum weight covers
- Unfolded graphs

## ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)