%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "kargers96.ltx",
%%%     date      = "27 September 1996",
%%%     time      = "14:44:17 EDT",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "07169 124 567 4610",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{KargerS96}

\title{A New Approach to the Minimum Cut Problem}

\author{David~R. Karger \and Clifford Stein}

\Pages{601--640}

\Month{July}

\Year{1996}

\Volume{43}

\Number{4}

\maketitle

\begin{abstract}

This paper presents a new approach to finding the minimum cuts in
undirected graphs. The fundamental principle is simple: the edges in a
graph's minimization 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
$\tilde{O}(mn)$ time bounds based on maximum flows. It is simple and
intuitive and used no complex data structures. Our algorithm can be
parallelized to run in $\mathcal{RNC}$ with $n^2$ processors; this
gives the first proof that the minimum cut problem can be solved in
$\mathcal{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
$\tilde{O}(n^{2\alpha})$ time, or in $\mathcal{RNC}$ with
$n^{2\alpha}$ processors. The problem of finding a minimum multiway
cut of a graph into $r$ pieces is solved in expected
$\tilde{O}(n^{2(r-1)})$ time, or in $\mathcal{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 representation
for minimum cuts.

\end{abstract}

\begin{categories}

F.2.2 [\textbf{Analysis of Algorithms and Problem Complexity}]:
Nonnumerical Algorithms and Problems; G.2.2 [\textbf{Discrete
Mathematics}]: Graph Theory---\emph{graph algorithms\textup; network
problems}; G.3 [\textbf{Probability and
Statistics}]---\emph{probabilistic algorithms \textup(including Monte
Carlo\textup)}; I.1.2 [\textbf{Algebraic Manipulation}]: Algorithms

\end{categories}

\begin{terms}

Algorithms

\end{terms}

\begin{keywords}

Graph algorithm, minimum cut, network reliability, parallel computing,
  randomized algorithm

\end{keywords}

\end{document}
