A near-linear time algorithm for constructing a cactus representation of minimum cuts
Lists
Only you see this
Abstract
We present an Õ(m) (near-linear) time Monte Carlo algorithm for constructing the cactus data structure, a useful representation of all the global minimum edge cuts of an undirected graph. Our algorithm represents a fundamental improvement over the best previous (quadratic time) algorithms: because there can be quadratically many min-cuts, our algorithm must avoid looking at all min-cuts during the construction, but nonetheless builds a data structure representing them all. Our result closes the gap between the (near-linear) time required to find a single min-cut and that for (implicitly) finding all the min-cuts.
BibTeX
@inproceedings{karger2009near,
author = {David R. Karger and Debmalya Panigrahi},
title = {{A near-linear time algorithm for constructing a cactus representation of minimum cuts}},
booktitle = {SODA},
year = {2009},
doi = {10.1137/1.9781611973068.28},
}Loading related content...