A Decomposition Theorem for Maximum Weight Bipartite Matchings

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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(sqrt(n)W/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.
The journal version will appear in SIAM Journal on Computing. The conference version appeared in ESA 1999

Keywords

Data Structures and Algorithms, Discrete Mathematics, E1; F2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30454

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0011015
 http://arxiv.org/abs/cs/0011015

Collections

arXiv