Odd minimum cut sets and b-matchings revisited

Details Odd minimum cut sets and b-matchings revisited Odd minimum cut sets and b-matchings revisited

2006-07-04

arxiv.org/abs/math/0607088v1

Mathematics

Optimization and Control

6 pages. An extended abstract of an earlier version appeared in Proc. IPCO X (2004)

Scientific paper

The famous Padberg-Rao separation algorithm for b-matching polyhedra can be implemented to run in O(n^2m log(n^2/m)) time in the uncapacitated case, and in O(nm^2 log(n^2/m)) time in the capacitated case (where n is the number of vertices and m is the number of edges of the underlying graph). We give a new and simple algorithm for the capacitated case which can be implemented to run in O(n^2m log(n^2/m)) time.

Affiliated with

Also associated with

No associations

Rating

Odd minimum cut sets and b-matchings revisited 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 Odd minimum cut sets and b-matchings revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Odd minimum cut sets and b-matchings revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-240116