Constructing a cactus for minimum cuts of a graph in O (mn+n(2) log n) time and O(m) Space
It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn + n(2) log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.
cactus minimum cut graph connectivity algorithm maximum adjacency ordering maximum flow