Access Restriction

Author Karger, David R. ♦ Stein, Clifford
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1996
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Graph algorithm ♦ Minimum cut ♦ Network reliability ♦ Parallel computing ♦ Randomized algorithm
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 $\textit{O(n2log3n)}$ time, a significant improvement over the previous $\textit{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 $\textit{RNC}$ with $\textit{n2}$ processors; this gives the first proof that the minimum cut problem can be solved in $\textit{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 α of the minimum cut's in expected $\textit{O˜(n2α)}$ time, or in $\textit{RNC}$ with $\textit{n2α}$ processors. The problem of finding a minimum multiway cut of graph into $\textit{r}$ pieces is solved in expected $\textit{O˜(n2(r-1))}$ time, or in $\textit{RNC}$ with $\textit{n2(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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1996-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 43
Issue Number 4
Page Count 40
Starting Page 601
Ending Page 640

Open content in new tab

   Open content in new tab
Source: ACM Digital Library