Canonical cactus representation for miminum cuts (Q1343494)

It is known that all minimum cuts in a network \(N\) can be embedded in a cactus whose size is bounded by a linear function of the number of vertices in \(N\). However, such a representation is not unique. In this paper, the authors have introduced two canonical forms of a cactus representation named the `cycle-type' and `junction-type' and have shown their uniqueness. It is also shown that these cacti contain at most twice as many vertices as \(N\). Such a unique representation is helpful in designing an efficient algorithm for constructing a cactus representation for all the minimum cuts of a given network.