A new approach to the minimum cut problem. Karger, D. R. & Stein, C. J ACM, 43(4):601–640, ACM press, New York, New York, NY, USA, 1996.
This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum 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 $O~(mn)$ time bounds based on maximum flows. It is simple and intuitive and uses 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 alpha of the minimum cut's in expected $O~(n^{2α})$ time, or in RNC with $2^{2α}$ processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected $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 representing for minimum cuts.
@Article{karger96new,
author    = {Karger, David R. and Stein, Clifford},
title     = {A new approach to the minimum cut problem},
journal   = {J ACM},
year      = {1996},
volume    = {43},
number    = {4},
pages     = {601--640},
issn      = {0004-5411},
abstract  = {This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum 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 $O~(mn)$ time bounds based on maximum flows. It is simple and intuitive and uses 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 alpha of the minimum cut's in expected $O~(n^{2\alpha})$ time, or in RNC with $2^{2\alpha}$ processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected $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 representing for minimum cuts.},
address   = {New York, NY, USA},
doi       = {10.1145/234533.234534},
owner     = {Sebastian},
publisher = {ACM press, New York},
timestamp = {2010.07.04},
}