doi abstract bibtex

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}, }

Downloads: 0