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.