Experimental study of minimum cut algorithms

Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein

Research output: Contribution to conferencePaperpeer-review

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 the worst-case time bounds for the problem. In this paper, we conduct experimental evaluation the relative performance of these algorithms. In the process, we develop heuristics and data structures that substantially improve the practical performance of the algorithms. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of the practical performance of minimum cut algorithms and produces very efficient codes for the problem.

Original languageEnglish (US)
Pages324-332
Number of pages9
StatePublished - Jan 1 1997
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997

Other

OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Experimental study of minimum cut algorithms'. Together they form a unique fingerprint.

Cite this