Efficient data structures for incremental exact and approximate maximum flow
Goranci G, Henzinger MH. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 69.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Goranci, Gramoz;
Henzinger, MonikaISTA 
Department
Grant
Series Title
LIPIcs
Abstract
We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.
Publishing Year
Date Published
2023-07-01
Proceedings Title
50th International Colloquium on Automata, Languages, and Programming
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Acknowledgement
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No.
101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the
Austrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”,
I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.
This work was done in part while Gramoz Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There, he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their insightful comments.
Volume
261
Article Number
69
Conference
ICALP: International Colloquium on Automata, Languages, and Programming
Conference Location
Paderborn, Germany
Conference Date
2023-07-10 – 2023-07-14
ISBN
ISSN
IST-REx-ID
Cite this
Goranci G, Henzinger MH. Efficient data structures for incremental exact and approximate maximum flow. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.69
Goranci, G., & Henzinger, M. H. (2023). Efficient data structures for incremental exact and approximate maximum flow. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69
Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
G. Goranci and M. H. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
Goranci G, Henzinger MH. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 69.
Goranci, Gramoz, and Monika H. Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2023_LIPIcsICALP_Goranci.pdf
875.91 KB
Access Level
Open Access
Date Uploaded
2023-08-21
MD5 Checksum
074177e815a1656de5d4071c7a3dffa6
Google Scholar
ISBN Search