Constructing a Cactus for Minimum Cuts of a Graph in O(mn+n2log 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>>
Buy this Article




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+n2log 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.