---
_id: '14085'
abstract:
- lang: eng
  text: 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.
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.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
  (MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic
  Hierarchical Graph Decompositions”,\r\nI 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.\r\nThis 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."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Goranci G, Henzinger M. Efficient data structures for incremental exact and
    approximate maximum flow. In: <i>50th International Colloquium on Automata, Languages,
    and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2023. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.69">10.4230/LIPIcs.ICALP.2023.69</a>'
  apa: 'Goranci, G., &#38; Henzinger, M. (2023). Efficient data structures for incremental
    exact and approximate maximum flow. In <i>50th International Colloquium on Automata,
    Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.69">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>'
  chicago: Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental
    Exact and Approximate Maximum Flow.” In <i>50th International Colloquium on Automata,
    Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.69">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>.
  ieee: G. Goranci and M. Henzinger, “Efficient data structures for incremental exact
    and approximate maximum flow,” in <i>50th International Colloquium on Automata,
    Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.
  ista: 'Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact
    and approximate maximum flow. 50th International Colloquium on Automata, Languages,
    and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261,
    69.'
  mla: Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental
    Exact and Approximate Maximum Flow.” <i>50th International Colloquium on Automata,
    Languages, and Programming</i>, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2023, doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.69">10.4230/LIPIcs.ICALP.2023.69</a>.
  short: G. Goranci, M. Henzinger, in:, 50th International Colloquium on Automata,
    Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2023.
conference:
  end_date: 2023-07-14
  location: Paderborn, Germany
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-06-04T07:19:37Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.69
ec_funded: 1
external_id:
  arxiv:
  - '2211.09606'
file:
- access_level: open_access
  checksum: 074177e815a1656de5d4071c7a3dffa6
  content_type: application/pdf
  creator: dernst
  date_created: 2023-08-21T06:59:05Z
  date_updated: 2023-08-21T06:59:05Z
  file_id: '14089'
  file_name: 2023_LIPIcsICALP_Goranci.pdf
  file_size: 875910
  relation: main_file
  success: 1
file_date_updated: 2023-08-21T06:59:05Z
has_accepted_license: '1'
intvolume: '       261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - '9783959772785'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient data structures for incremental exact and approximate maximum flow
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...