2000/11/11 by Ming-Yang Kao, Tak-Wah Lam, Kao, Ming-Yang +5
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #E1 #F2.2 #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0011015
The journal version will appear in SIAM Journal on Computing. The conference version appeared in ESA 1999
arxiv created 2000/11/11 · arxiv updated 2009/11/30
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(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.