Odd minimum cut-sets and b-matchings revisited
A N Letchford
G Reinelt
D O Theis
| Publication date | 2008 |
| Original language | English |
Abstract
The famous Padberg–Rao separation algorithm for b-matching polyhedra can be implemented to run in O(|V|^2|E| log(|V|^2/|E|)) time in the uncapacitated case, and in O(|V||E|^2 log(|V|^2/|E|)) time in the capacitated case. We give a new and simple algorithm for the capacitated case which can be implemented to run in O(|V|^2|E|\log(|V|^2/|E|)) time.
