A decomposition theorem for maximum weight bipartite matchings

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. © 2001 Society for Industrial and Applied Mathematics.