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.