Odd Minimum Cut Sets and b -Matchings Revisited
Adam N. Letchford, Gerhard Reinelt, Dirk Oliver Theis · SIAM Journal on Discrete Mathematics · 2008
The famous Padberg–Rao separation algorithm for b-matching polyhedra can be implemented to run in $\mathcal{O}(|V|^2|E|\log(|V|^2/|E|))$ time in the uncapacitated case, and in $\mathcal{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 $\mathcal{O}(|V|^2|E|\log(|V|^2/|E|))$ time.