EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Incremental Approximate Maximum Flow via Residual Graph Sparsification

Gramoz Goranci, Monika Henzinger, Harald Räcke, A. R. Sricharan

ACM Transactions on Algorithms · 31.07.2026 · 22 (3) · 1-24

DOI: 10.1145/3816252 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 06.07.2026. Verfasst von Gramoz Goranci und 3 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Austrian Science Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We give an algorithm that, with high probability, maintains a \((1-\varepsilon)\) -approximate \(s\text{-}t\) maximum flow in undirected, uncapacitated \( n \) -vertex graphs undergoing \( m \) edge insertions in \(\tilde{O}(m+nF^{*}/\varepsilon)\) total update time, where \(F^{*}\) is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ( \(m=\Omega(n^{2})\) ), and more generally, for graphs where \(F^{*}=\tilde{O}(m/n)\) . At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC ’02, SICOMP ’15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC ’11, SICOMP ’19] from undirected graphs to balanced directed graphs.

Förderung

  • European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
  • Austrian Science Fund

Zitieren

APA

Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. R. (2026). Incremental Approximate Maximum Flow via Residual Graph Sparsification. ACM Transactions on Algorithms, 22(3), 1-24. https://doi.org/10.1145/3816252

Vancouver

Goranci G, Henzinger M, Räcke H, Sricharan AR. Incremental Approximate Maximum Flow via Residual Graph Sparsification. ACM Transactions on Algorithms. 2026;22(3):1-24. doi:10.1145/3816252

BibTeX
@article{Goranci2026,
  author = {Goranci, Gramoz and Henzinger, Monika and Räcke, Harald and Sricharan, A. R.},
  title = {Incremental Approximate Maximum Flow via Residual Graph Sparsification},
  journal = {ACM Transactions on Algorithms},
  year = {2026},
  volume = {22},
  number = {3},
  pages = {1--24},
  doi = {10.1145/3816252}
}
Kostenlos starten →