Incremental approximate maximum flow in m1/2+o(1) update time
Goranci G, Henzinger M. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv, 2211.09606.
Download (ext.)
Preprint
| Submitted
| English
Author
Goranci, Gramoz;
Henzinger, MonikaISTA 
Abstract
We show an $(1+\epsilon)$-approximation algorithm for maintaining maximum $s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)} \epsilon^{-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
2022-11-17
Journal Title
arXiv
Article Number
2211.09606
IST-REx-ID
Cite this
Goranci G, Henzinger M. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv. doi:10.48550/arXiv.2211.09606
Goranci, G., & Henzinger, M. (n.d.). Incremental approximate maximum flow in m1/2+o(1) update time. arXiv. https://doi.org/10.48550/arXiv.2211.09606
Goranci, Gramoz, and Monika Henzinger. “Incremental Approximate Maximum Flow in M1/2+o(1) Update Time.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2211.09606.
G. Goranci and M. Henzinger, “Incremental approximate maximum flow in m1/2+o(1) update time,” arXiv. .
Goranci G, Henzinger M. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv, 2211.09606.
Goranci, Gramoz, and Monika Henzinger. “Incremental Approximate Maximum Flow in M1/2+o(1) Update Time.” ArXiv, 2211.09606, doi:10.48550/arXiv.2211.09606.
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 2211.09606
Google Scholar