cshjin / mincutalgo Goto Github PK

Paper: Karger, David R., and Debmalya Panigrahi. "A near-linear time algorithm for constructing a cactus representation of minimum cuts." Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2009.

Abs:
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.

Should compare FastMinCut(graph_1) and FastMinCut(graph_2), rather than graph_1 and graph_2