Practical Performance of Efficient Minimum Cut Algorithms

Jünger, Michael and Rinaldi, Giovanni and Thienel, Stefan (2000) Practical Performance of Efficient Minimum Cut Algorithms.
Published in: Algorithmica Vol. 26 (1). pp. 172-195.

Abstract

In the late eighties and early nineties, three major exciting new developments (and some ramifications) in the computation of minimum capacity cuts occurred and these developments motivated us to evaluate the old and new methods experimentally. We provide a brief overview of the most important algorithms for the minimum capacity cut problem and compare these methods both on problem instances from the literature and on problem instances originating from the solution of the traveling salesman problem by branch-and-cut.


Actions:
Download: [img] Postscript - Preprinted Version
Download (705kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 25 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Uncontrolled Keywords: graph algorithms, minimum cut algorithms
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 10 Jun 2003 00:00
Last Modified: 16 Jan 2012 14:08
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 10 Jun 2003 00:00
Last Modified: 16 Jan 2012 14:08
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/271