---
res:
  bibo_abstract:
  - We give an algorithm that, with high probability, maintains a (1-ε)-approximate
    s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge
    insertions in Õ(m+ n F^*/ε) 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 = Ω(n²)), and more generally, for graphs where
    F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph
    sparsification technique of Karger and Levine [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. [SICOMP '19] from undirected graphs to balanced directed graphs.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Gramoz
      foaf_name: Goranci, Gramoz
      foaf_surname: Goranci
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Harald
      foaf_name: Räcke, Harald
      foaf_surname: Räcke
  - foaf_Person:
      foaf_givenName: A. R.
      foaf_name: Sricharan, A. R.
      foaf_surname: Sricharan
  bibo_doi: 10.1145/3816252
  bibo_issue: '3'
  bibo_volume: 22
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1549-6325
  - http://id.crossref.org/issn/1549-6333
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Incremental approximate maximum flow via residual graph sparsification@
...