Disjoint (s, t)‐cuts in a network

Consider a graph having distinguished vertices s and t , and a nonnegative, real‐valued cost associated with each edge. This paper considers variations on the problem of finding k pairwise‐disjoint ( s, t )‐cuts of minimum total cost. For k = 1, this problem is a version of the well‐known minimum‐cut problem from network‐flow theory and, thus, is solvable in polynomial time. The main result of this paper is that for arbitrary k , the problem can be formulated as a specially structured transshipment problem and, thus, is solvable in polynomial time.