Practical minimum cut algorithms
Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA
;
Noe, Alexander;
Schulz, Christian;
Strash, Darren
![](https://research-explorer.ista.ac.at/images/icon_orcid.png)
Abstract
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.
Publishing Year
Date Published
2018-01-01
Proceedings Title
20th Workshop on Algorithm Engineering and Experiments
Page
48-61
Conference
ALENEX: Symposium on Algorithm Engineering and Experiments
Conference Location
New Orleans, LA, United States
Conference Date
2018-01-07 – 2018-01-08
IST-REx-ID
Cite this
Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. In: 20th Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2018:48-61. doi:10.1137/1.9781611975055.5
Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2018). Practical minimum cut algorithms. In 20th Workshop on Algorithm Engineering and Experiments (pp. 48–61). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975055.5
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” In 20th Workshop on Algorithm Engineering and Experiments, 48–61. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975055.5.
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” in 20th Workshop on Algorithm Engineering and Experiments, New Orleans, LA, United States, 2018, pp. 48–61.
Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.
Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” 20th Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2018, pp. 48–61, doi:10.1137/1.9781611975055.5.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1708.06127