### A new approach to the minimum cut problemA new approach to the minimum cut problem

Access Restriction
Subscribed

 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

Source: ACM Digital Library