A cactus is a simple data structure that represents all minimum cuts of a weighted, undirected graph in linear space. We describe the first algorithm that can build a cactus from the asymptotically fastest deterministic algorithm that finds all minimum cuts in a weighted graph-the Hao-Orlin minimum cut algorithm. This improves the deterministic time to construct the cactus in graphs with n vertices and In edges from O(n(3)) to O(nm log n(2)/nt). (C) 1999 Academic Press.
['Lisa Fleischer']
Building Chain and Cactus Representations of All Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time