Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Odd minimum cut-sets and b-matchings revisited
AU - Letchford, A N
AU - Reinelt, G
AU - Theis, D O
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - matching
KW - polyhedra
KW - separation
U2 - 10.1137/060664793
DO - 10.1137/060664793
M3 - Journal article
VL - 22
SP - 1480
EP - 1487
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
SN - 0895-4801
IS - 4
ER -