	      Implementations of Minimum Cut Algorithms

DESCRIPTION

This package contains implementations of four recent algorithms for
the minimum cut problem and associated problem generators, as
described in "Experimental Study of Minimum Cut Algorithms", in
proceedings of the 8th Annual Symposium on Discrete Algorithms, 1997.
There is also a longer, more detailed version of the paper available
at http://theory.lcs.mit.edu/~mslevine/mincut/index.html

The cut programs all take graphs in DIMACS format on stdin and output
the value of the minimum cut, the time taken to find it, and various
stats on stdout. It shouldn't be hard to modify the code to
output the actual cut. (In some cases the code for it is there, but it
is untested.) See the README in the source directory for more info.

AUTHORS

Chandra Chekuri		mailto:chekuri@theory.stanford.edu
			http://theory.stanford.edu/people/chekuri
Andrew Goldberg		mailto:avg@research.nj.nec.com
			http://www.neci.nj.nec.com/homepages/avg.html
David Karger		mailto:karger@theory.lcs.mit.edu 
			http://theory.lcs.mit.edu/~karger
Matthew Levine		mailto:mslevine@theory.lcs.mit.edu
			http://theory.lcs.mit.edu/~mslevine
Cliff Stein		mailto:cliff@cs.dartmouth.edu
			http://www.cs.dartmouth.edu/~cliff

FILES/SUBDIRECTORIES

README		this file
COPYRIGHT	copying policy
bin		dir for compiled binaries
inputs		some TSP inputs courtesy of Applegate and Cook
results		dir for results
scripts		dir with scripts for testing codes
src		dir with C source code

INSTALL

The makefile in the src subdirectory builds the 4 programs with
various options, as well as the generators. The command 'make install'
will make all the binaries and copy them to the bin subdirectory.

The codes take advantage of features present in gcc, but they should
compile with any ANSI C compiler. If your system doesn't have getopt.h
(eg, it is a Sun), you'll need to uncomment -DBROKEN_HDRS on the
CFLAGS line in the makefile in order to get some of the programs to
compile.

See the README in the src directory for more info.

AVAILABILITY

This package should be available at 
http://theory.lcs.mit.edu/~mslevine/mincut/index.html

It is for non-commercial use only.

$Id: README,v 1.2 1997/03/05 15:34:09 mslevine Exp $