A Decomposition Theorem for Maximum Weight Bipartite Matchings

Details A Decomposition Theorem for Maximum Weight Bipartite Matchings A Decomposition Theorem for Maximum Weight Bipartite Matchings

2000-11-11

arxiv.org/abs/cs/0011015v1

Computer Science

Data Structures and Algorithms

The journal version will appear in SIAM Journal on Computing. The conference version appeared in ESA 1999

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Decomposition Theorem for Maximum Weight Bipartite Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Decomposition Theorem for Maximum Weight Bipartite Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Decomposition Theorem for Maximum Weight Bipartite Matchings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-452609