The construction of a cactus representation for all minimum cuts in an edge-weighted, undirected network is studied in this paper. Given such a network with a set V of vertices and a set E of edges, the previously known algorithms for constructing a cactus representation require solving ℝVℝ-1 maximum flow problems, each with a prescribed pair of source and sink, in order to find all minimum cuts that separate them. The authors first show that computing a maximum flow between a pair of vertices, s and t, reveals many other minimum cuts that do not separate s and t. Based on this fact, they propose a new algorithm that can choose an arbitrary pair of source and sink for each maximum flow problem. For a network with unit edge weights, the present algorithm runs in O(ℝEℝ+λℝVℝ2) time, where λ is the weight of a minimum cut.
