These are the abstracts of the papers available in this directory.


%%%%%%% approxcut.ps

\title{
Parallel and Dynamic Algorithms for Approximating Minimum Cuts
}

\begin{abstract}
We develop new parallel and dynamic algorithms for approximating
minimum cuts in weighted, undirected graphs.  Our approach is to
combine new algorithms for sparse unweighted graphs with a reduction
for dense weighted graphs called {\em randomized sparsification}.
Randomized sparsification yields a sparse unweighted graph which
closely approximates the minimum cut structure of the original graph.
In~\cite{Karger:Skeleton}, this techniques was used in sequential
algorithms for approximating the minimum cut.  In this paper we devise
parallel and dynamic approximation algorithms.  We show that a cut
within a multiplicative factor of $\alpha$ of the minimum can be found
in $\RNC$ using $m+n^{2/\alpha}$ processors.  Using similar
techniques, we give a {\em dynamic approximation algorithm} for a
graph undergoing a series of edge insertions and deletions.  At a cost
of $\Olog(n/\epsilon^2)$ time per insertion or deletion, the
algorithm will maintain a cut with value at most $(1+\epsilon)$ times
the minimum.

We also consider a functional inverse of randomized sparsification,
and use it to develop a different dynamic algorithm which approximates
the value of the minimum cut more quickly than the previous algorithm,
but does not actually exhibit a cut of small value.  An
$O(\sqrt{1+2/\epsilon})$-approximation to the minimum cut value is
maintained at a cost of $\Olog(n^{\epsilon+1/2})$ time per insertion
or deletion.  If only insertions are allowed, the approximation can be
maintained at a cost of $\Olog(n^{\epsilon})$ time per insertion.
\end{abstract}

%%%%%%%%%%%%%%   mincut.ps

\def\Mincut{
``Global Min-cuts in $\RNC$, and Other Ramifications of a Simple Min-cut
Algorithm.'' {\it Proceedings of the $4^{th}$ Annual
SIAM Symposium on Data Structures and Algorithms}, 1993.

\abst{

This paper first presented the Contraction Algorithm.  This algorithm
was the first $\RNC$ (\ie, efficiently parallelizable) algorithm for
finding minimum cuts in unweighted graphs.  It extends to solving the
minimum multi-way cut problem, \ie\ the problem of partitioning the
graph into some fixed number of pieces such that the total weight of
edges crossing between the pieces is minimized.  It also shows what
has turned out to be a very useful result on the structure of cuts in
a graph, namely that the number of cuts with value within a factor of
$\alpha$ of the minimum cut is at most $n^{2\alpha}$, and gives an
efficient algorithm for finding all such cuts.
}}


%%%%%%%%%%%%%   fastcut.ps

\def\Fastcut{
``An $\tilde{O}(n^2)$ Algorithm for Minimum Cuts,'' with
Clifford Stein.  {\it Proceedings of the $25^{th}$ Annual ACM Symposium
on Theory of Computing}, 1993.

\abst{
This paper improves the efficiency of the Contraction Algorithm so
that it runs in $\Olog(n^2)$ time or in parallel in $\RNC$ using only $n^2$
processors.  This makes it the most efficient sequential or parallel
algorithm for the minimum cut problem and demonstrates that minimum
cuts might be easier to solve than maximum flows.
}}


%%%%%%%%%%%%%  approxcut.ps

\def\Approxcut{
``Using Randomized Sparsification to Approximate Minimum Cuts
Sequentially, Dynamically, and in Parallel.''  
{\it Proceedings of the $5^{th}$ SIAM Symposium on Data
Structures and Algorithms}, 1994.

\abst{
The structure of cuts demonstrated by the Contraction Algorithm is
used to develop new algorithms for approximating the minimum cut.  A
sequential algorithm presented there approximates the minimum cut
value to within any constant factor in linear time.  A similar
parallel algorithm approximates the cut using a linear number of
processors.  A dynamic algorithm maintains a factor of 2 approximation
to the minimum cut while edges are added to and deleted from a graph.
The time needed per update is $O(\log n)$ if only edge insertions are
allowed, and $O(\sqrt{n})$ if both insertions and deletions are
permitted.}}

%%%%%%%%%%%%%  skeleton.ps

\def\Skeleton{
``Random Sampling in Cut, Flow, and Network Design Problems.''
To appear in {\it Proceedings of the $26^{th}$ Annual ACM Symposium on the
Theory of Computing}, 1994.

\abst{
We extend the work of the previous paper, and show that random
sampling is a powerful tool for many other problems involving cuts in
unweighed graphs.  For example, we give algorithms for approximating
or exactly finding $s$-$t$ minimum cuts.  In unweighted graphs, if the
minimum cut has value $c$ and the $s$-$t$ minimum cut has value $v$,
then the $s$-$t$ minimum cut can be approximated to within any
constant factor in $O(mv/c^2)$ time.  An approximately maximum $s$-$t$
flow can be found in $O(mv/c)$ time.  A maximum $s$-$t$ flow can be
found in $O(mv/\sqrt{c})$ time.  Previously, there were no
approximation algorithms known and the best exact algorithm ran in
$O(mv)$ time.  A global minimum cut can be found in $O(m\sqrt{c})$
time.  This improves on the previous $O(mc)$ time bound.  We give a
simple algorithm for the $k$-connected orientation problem and give
improved approximation algorithms for the minimum $k$-connected
subgraph problem.}}

%%%%%%%%%%%%%%% detcut.ps

\def\Detcut{
``Derandomization through Approximation: An ${\cal NC}$ Algorithm for
Minimum Cuts,'' with Rajeev Motwani.  Stanford Technical Report
STAN-CS-93-1471.  To appear in {\it Proceedings of the $26^{th}$
Annual ACM Symposium on Theory of Computing}, 1994.

\abst{
This paper gives the first deterministic parallel algorithm for the
minimum cut problem.  This is not a derandomization of the Contraction
Algorithm, but instead a derandomization of a completely different
algorithm whose proof of correctness depends upon the Contraction
Algorithm.  To perform the derandomization, we had to develop new
techniques which may be applicable in other problems.
}}


%%%%%%%%%%%%%%% matroid.ps

\def\Matroid{

Journal version of

``Random Sampling in Matroids, with Applications to Graph Connectivity
and Minimum Spanning Trees.''  {\it Proceedings of
the $34^{th}$ Annual Symposium on Foundations of Computer Science}, 1993.

\abst{
Random sampling is a powerful tool for gathering information about a
group by considering only a small part of it.  We discuss some broadly
applicable paradigms for using random sampling in combinatorial
optimization, and demonstrate the effectiveness of these paradigms for
several optimization problems.  Perhaps the best known problem we
address is that of finding a {\em minimum spanning tree (MST)}.  We
apply random sampling in a fast and practical algorithm for finding an
{\em approximately} minimum spanning tree of a graph.  We then show
how to find a minimum spanning tree by approximating the solution and
then ``repairing'' the approximation.  We originally showed that this
algorithm runs in $O(m+n\log n)$ time with high probability.  Klein
and Tarjan have recently shown that in fact this algorithm runs in
linear time with high probability, thus giving the first linear time
minimum spanning tree algorithm for the comparison model of
computation.  We include their analysis here.

We generalize the random sampling approach in several directions.  We
show how it can be used to improve the efficiency of parallel
algorithms for the MST problem, and in particular give the first time
and work optimal parallel MST algorithm for the CREW PRAM on dense
graphs.

We also apply random sampling to problems involving matroids.  We
reduce the problem of finding an optimum matroid basis to the problem
of verifying that a given basis is optimal, showing that the two
problems can be solved in roughly the same time.  As an example, we
give a new algorithm for a widely discussed task scheduling problem
which can be formulated as matroid optimization.  We also address the
problem of packing bases in a matroid, also known as matroid
partitioning.  By generalizing certain results from random graph
theory, we show how random sampling gives fast approximations
and exact algorithms.  Our techniques have also been effective for
other packing problems.  We give particular attention to the problem
of packing spanning trees in graphs, which has applications in network
reliability analysis.
}}