Access Restriction

Author Karger, David R.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Monte Carlo algorithm ♦ Connectivity ♦ Min-cut ♦ Optimization ♦ Tree packing
Abstract We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an $\textit{m}-edge,$ $\textit{n}-vertex$ graph with high probability in $\textit{O}(m$ log3 $\textit{n})$ time. We also give a simpler randomized algorithm that finds $\textit{all}$ minimum cuts with high probability in $O(\textit{m}$ log3 $\textit{n})$ time. This variant has an optimal $\textit{RNC}$ parallelization. Both variants improve on the previous best time bound of O(n2 log3 n). Other applications of the tree-packing approach are new, nearly tight bounds on the number of $\textit{near-minimum}$ cuts a graph may have and a new data structure for representing them in a space-efficient manner.
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 2000-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 47
Issue Number 1
Page Count 31
Starting Page 46
Ending Page 76

Open content in new tab

   Open content in new tab
Source: ACM Digital Library