Practical fully dynamic minimum cut algorithms

Henzinger MH, Noe A, Schulz C. 2022. Practical fully dynamic minimum cut algorithms. 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 13–26.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Henzinger, MonikaISTA ; Noe, Alexander; Schulz, Christian
Abstract
We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a fully-dynamic algorithm. The algorithm uses the theoretical foundation and combines it with efficient and finely-tuned implementations to give an algorithm that can maintain the global minimum cut of a graph with rapid update times. We show that our algorithm gives up to multiple orders of magnitude speedup compared to static approaches both on edge insertions and deletions.
Publishing Year
Date Published
2022-01-01
Proceedings Title
2022 Proceedings of the Symposium on Algorithm Engineering and Experiments
Publisher
Society for Industrial and Applied Mathematics
Page
13-26
Conference
ALENEX: Symposium on Algorithm Engineering and Experiments
Conference Location
Alexandria, VA, United States
Conference Date
2022-01-09 – 2022-01-10
IST-REx-ID

Cite this

Henzinger MH, Noe A, Schulz C. Practical fully dynamic minimum cut algorithms. In: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2022:13-26. doi:10.1137/1.9781611977042.2
Henzinger, M. H., Noe, A., & Schulz, C. (2022). Practical fully dynamic minimum cut algorithms. In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (pp. 13–26). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977042.2
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Practical Fully Dynamic Minimum Cut Algorithms.” In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, 13–26. Society for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/1.9781611977042.2.
M. H. Henzinger, A. Noe, and C. Schulz, “Practical fully dynamic minimum cut algorithms,” in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2022, pp. 13–26.
Henzinger MH, Noe A, Schulz C. 2022. Practical fully dynamic minimum cut algorithms. 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 13–26.
Henzinger, Monika H., et al. “Practical Fully Dynamic Minimum Cut Algorithms.” 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2022, pp. 13–26, doi:10.1137/1.9781611977042.2.
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
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2101.05033

Search this title in

Google Scholar