Journal of the ACM Bibliography

David R. Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, July 1996. [BibTeX entry]
Abstract

This paper presents a new approach to finding the minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimization cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n^2 log^3 n) time, a significant improvement over the previous \tilde{O}(mn) time bounds based on maximum flows. It is simple and intuitive and used no complex data structures. Our algorithm can be parallelized to run in RNC with n^2 processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.

With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of a of the minimum cut's in expected \tilde{O}(n^{2a}) time, or in RNC with n^{2a} processors. The problem of finding a minimum multiway cut of a graph into r pieces is solved in expected \tilde{O}(n^{2(r-1)}) time, or in RNC with n^{2(r-1)} processors. The trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representation for minimum cuts.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, network problems; G.3 [Probability and Statistics] -- probabilistic algorithms (including Monte Carlo); I.1.2 [Algebraic Manipulation]: Algorithms

General Terms: Algorithms

Additional Key Words and Phrases: Graph algorithm, minimum cut, network reliability, parallel computing, randomized algorithm

Selected papers that cite this one

Selected references

Shortcuts:

• Journal of the ACM homepage
• Bibliography top level
• Journal of the ACM Author Index
• Search the HBP database