Parijat Dube, Joao P.M. Goncalves, et al.
WSC 2014
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.
Parijat Dube, Joao P.M. Goncalves, et al.
WSC 2014
Francisco Barahona, Fabián A. Chudak
Discrete Optimization
Francisco Barahona
SIAM Journal on Optimization
Mourad Baïou, Francisco Barahona
Discrete Optimization