Fractional Packing of T-joins

Francisco Barahona (barahonus.ibm.com)

Abstract: Given a graph with nonnegative capacities on its edges, it is well known that the weight of a minimum T-cut is equal to the value of a maximum packing of T-joins. Padberg-Rao's algorithm finds a minimum weight T-cut but it does not produce a T-join packing, we present a polynomial combinatorial algorithm for finding an optimal T-join packing.

Keywords: T-joins, T-cuts

Category 1: Combinatorial Optimization

Citation:

Download: [PDF]

Entry Submitted: 06/18/2002
Entry Accepted: 06/18/2002
Entry Last Modified: 04/21/2004

Modify/Update this entry