Marcos Goycoolea, Alan T. Murray, et al.
Operations Research
Given a graph with nonnegative capacities on its edges, it is well known that the capacity of a minimum T-cut is equal to the value of a maximum fractional packing of T-joins. The Padberg-Rao algorithm finds a minimum capacity T-cut, but it does not produce a T-join packing. We present a polynomial combinatorial algorithm for finding an optimal T-join packing.
Marcos Goycoolea, Alan T. Murray, et al.
Operations Research
Francisco Barahona
Mathematical Programming
Mourad Baiou, Francisco Barahona
SIAM Journal on Discrete Mathematics
Rui S. Shibasaki, Mourad Baïou, et al.
Annals of Operations Research