For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/02/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Graph Algorithms
graph, minimum cut, algorithm, cactus, maximum adjacency ordering, connectivity, maximum flow,
Full Text: PDF(280.3KB)>>
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.