Experimental Study of Minimum Cut Algorithms
Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Clifford Stein · 1997
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 Foundation, Shell Foundation, and Xerox Corporation. y Research partly supported by ARPA contract N00014-95-1-1246. z Research partly supported by a grant from the World Wide Web Consortium. Some of this work was done while visiting the second author at ...