IEICE Trans - Constructing a Cactus for Minimum Cuts of a Graph in <I>O</I>(<I>mn</I>+<I>n</I><SUP>2</SUP>log <I>n</I>) Time and <I>O</I>(<I>m</I>) Space

Constructing a Cactus for Minimum Cuts of a Graph in O(mn+n²log n) Time and O(m) Space

Hiroshi NAGAMOCHI
Shuji NAKAMURA
Toshimasa ISHII

Publication
IEICE TRANSACTIONS on Information and Systems Vol.E86-D No.2 pp.179-185
Publication Date: 2003/02/01
Online ISSN:
DOI:
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Graph Algorithms
Keyword:
graph, minimum cut, algorithm, cactus, maximum adjacency ordering, connectivity, maximum flow,

Full Text: PDF>>

Summary:
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²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.