Finding all global minimum cuts in practice
Henzinger MH, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA 
;
Noe, Alexander;
Schulz, Christian;
Strash, Darren
;
Noe, Alexander;
Schulz, Christian;
Strash, DarrenSeries Title
LIPIcs
Abstract
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.
Publishing Year
Date Published
2020-08-26
Proceedings Title
28th Annual European Symposium on Algorithms
Volume
173
Article Number
59
Conference
ESA: Annual European Symposium on Algorithms
Conference Location
Pisa, Italy
Conference Date
2020-09-07 – 2020-09-09
ISBN
ISSN
IST-REx-ID
Cite this
Henzinger MH, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.59
Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2020). Finding all global minimum cuts in practice. In 28th Annual European Symposium on Algorithms (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.59
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.59.
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
Henzinger MH, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.
Henzinger, Monika H., et al. “Finding All Global Minimum Cuts in Practice.” 28th Annual European Symposium on Algorithms, vol. 173, 59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.ESA.2020.59.
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 2002.06948
Google Scholar
ISBN Search