A decomposition theorem for maximum weight bipartite matchings

Ming Yang Kao*, Tak Wah Lam, Wing Kin Sung, Hing Fung Ting

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

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(x2/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 languageEnglish (US)
Pages (from-to)18-26
Number of pages9
JournalSIAM Journal on Computing
Volume31
Issue number1
DOIs
StatePublished - 2001

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A decomposition theorem for maximum weight bipartite matchings'. Together they form a unique fingerprint.

Cite this