Mourad Baiou, Francisco Barahona
Mathematical Programming
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.
Mourad Baiou, Francisco Barahona
Mathematical Programming
Mourad Baiou, Francisco Barahona
SIAM Journal on Discrete Mathematics
Mourad Baïou, Francisco Barahona, et al.
SIAM Journal on Discrete Mathematics
Radu Marinescu, Haifeng Qian, et al.
IJCAI 2023