Department of Applied Mathematics & Physics, Kyoto Univiversity

### Technical Report #97012 (December, 1997) A Fast Algorithm for Cactus Representations of Minimum Cuts by Hiroshi Nagamochi, Yoshitaka Nakao and Toshihide Ibaraki

This paper presents an algorithm for constructing a cactus representation for all minimum cuts in an undirected network. Our algorithm runs in $O(nm+n^{2}\log n+\gamma m\log n)$ time, where $n$ and $m$ are the number of vertices and edges respectively, and $\gamma$ is the number of cycles in a cactus representation, which is the one of the best deterministic time complexities to compute a cactus representation.