language: en

Experimental Study of Minimum Cut Algorithms

Chandra S. Chekuri
Computer Science Department Stanford University
Stanford, CA 94305
chekuri@theory.stanford.edu
Andrew V. Goldberg
NEC Research Institute
Princeton, NJ 08540
avg@research.nj.nec.com
David R. Karger
Laboratory for Computer Science MIT
Cambridge, MA 02139
karger@theory.lcs.mit.edu
Matthew S. Levine
Laboratory for Computer Science MIT
Cambridge, MA 02139
mslevine@theory.lcs.mit.edu
Cliff Stein x
Department of Computer Science Dartmouth College
Hanover, NH, 03755
cliff@cs.dartmouth.edu. October 1996

Abstract Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case time bounds for the problem. We conduct experimental evaluation the relative performance of these algorithms. In the process, we develop heuristics and data structures that substantially improve practical performance of the algorithms. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of practical performance of the minimum cut algorithms and produces very efficient codes for the problem.

[Supported by NSF Award CCR-9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foun dation, Shell Foundation, and Xerox Corporation. Research partly supported by ARPA contract N00014-95-1-1246. Research partly supported by a grant from the World Wide Web Consortium. Some of this work was done while visiting the second author at NEC. x Research partly supported by NSF Award CCR-9308701, a Walter Burke Research Initiation Award and a Dartmouth College Research Initiation Award. Some of this work was done while visiting the second author at NEC, and while visiting Stanford University.]