Home > Research > Publications & Outputs > Odd minimum cut-sets and b-matchings revisited

Research

Links

Text available via DOI:

Keywords

View graph of relations

Odd minimum cut-sets and b-matchings revisited

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Odd minimum cut-sets and b-matchings revisited. / Letchford, A N; Reinelt, G; Theis, D O.
In: SIAM Journal on Discrete Mathematics, Vol. 22, No. 4, 2008, p. 1480-1487.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, AN, Reinelt, G & Theis, DO 2008, 'Odd minimum cut-sets and b-matchings revisited', SIAM Journal on Discrete Mathematics, vol. 22, no. 4, pp. 1480-1487. https://doi.org/10.1137/060664793

APA

Letchford, A. N., Reinelt, G., & Theis, D. O. (2008). Odd minimum cut-sets and b-matchings revisited. SIAM Journal on Discrete Mathematics, 22(4), 1480-1487. https://doi.org/10.1137/060664793

Vancouver

Letchford AN, Reinelt G, Theis DO. Odd minimum cut-sets and b-matchings revisited. SIAM Journal on Discrete Mathematics. 2008;22(4):1480-1487. doi: 10.1137/060664793

Author

Letchford, A N ; Reinelt, G ; Theis, D O. / Odd minimum cut-sets and b-matchings revisited. In: SIAM Journal on Discrete Mathematics. 2008 ; Vol. 22, No. 4. pp. 1480-1487.

Bibtex

@article{93276e066edc4dd685de0e14b68f1359,
title = "Odd minimum cut-sets and b-matchings revisited",
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.",
keywords = "matching, polyhedra, separation",
author = "Letchford, {A N} and G Reinelt and Theis, {D O}",
year = "2008",
doi = "10.1137/060664793",
language = "English",
volume = "22",
pages = "1480--1487",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "4",

}

RIS

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 -