Practical minimum cut algorithms
Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 23, 1–22.
Download (ext.)
https://arxiv.org/abs/1708.06127
[Preprint]
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Noe, Alexander;
Schulz, Christian;
Strash, Darren
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 runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate.
Keywords
Publishing Year
Date Published
2018-10-01
Journal Title
ACM Journal of Experimental Algorithmics
Publisher
Association for Computing Machinery
Volume
23
Page
1-22
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 2018;23:1-22. doi:10.1145/3274662
Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2018). Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. Association for Computing Machinery. https://doi.org/10.1145/3274662
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics. Association for Computing Machinery, 2018. https://doi.org/10.1145/3274662.
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” ACM Journal of Experimental Algorithmics, vol. 23. Association for Computing Machinery, pp. 1–22, 2018.
Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 23, 1–22.
Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics, vol. 23, Association for Computing Machinery, 2018, pp. 1–22, doi:10.1145/3274662.
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
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1708.06127