Disjoint (s, t)‐cuts in a network
Donald K. Wagner · Networks · 1990
Abstract 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.