Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Gramoz Goranci; Monika Henzinger

doi:10.4230/LIPIcs.ICALP.2023.69

Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Gramoz Goranci, Monika Henzinger

Research Group Theory and Applications of Algorithms

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

Abstract

We show an (1 + ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m ¹/2+o ⁽¹⁾ϵ ⁻¹/ ² 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. Furthermore we give an algorithm that maintains an exact maximum s-t flow under m edge insertions in an n-node graph in Õ(n ⁵/ ²) total update time. For sufficiently dense graphs, this gives to the first exact incremental algorithm with sub-linear amortized update time for maintaining maximum flows.

Original language	English
Title of host publication	50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Editors	Kousha Etessami, Uriel Feige, Gabriele Puppis
ISBN (Electronic)	9783959772785
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2023.69
Publication status	Published - 1 Jul 2023

Austrian Fields of Science 2012

102031 Theoretical computer science

Keywords

data structures
dynamic graph algorithms
maximum flow

Access to Document

10.4230/LIPIcs.ICALP.2023.69

http://eprints.cs.univie.ac.at/7763/

Cite this

@inproceedings{1231ff8b6ecf437b8e4c3ca4c4819806,

title = "Efficient Data Structures for Incremental Exact and Approximate Maximum Flow",

abstract = "We show an (1 + ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m 1/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. Furthermore we give an algorithm that maintains an exact maximum s-t flow under m edge insertions in an n-node graph in {\~O}(n 5/ 2) total update time. For sufficiently dense graphs, this gives to the first exact incremental algorithm with sub-linear amortized update time for maintaining maximum flows.",

keywords = "data structures, dynamic graph algorithms, maximum flow",

author = "Gramoz Goranci and Monika Henzinger",

year = "2023",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.ICALP.2023.69",

language = "English",

editor = "Kousha Etessami and Uriel Feige and Gabriele Puppis",

booktitle = "50th International Colloquium on Automata, Languages, and Programming, ICALP 2023",

}

TY - GEN

T1 - Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

AU - Goranci, Gramoz

AU - Henzinger, Monika

PY - 2023/7/1

Y1 - 2023/7/1

N2 - We show an (1 + ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m 1/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. Furthermore we give an algorithm that maintains an exact maximum s-t flow under m edge insertions in an n-node graph in Õ(n 5/ 2) total update time. For sufficiently dense graphs, this gives to the first exact incremental algorithm with sub-linear amortized update time for maintaining maximum flows.

AB - We show an (1 + ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m 1/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. Furthermore we give an algorithm that maintains an exact maximum s-t flow under m edge insertions in an n-node graph in Õ(n 5/ 2) total update time. For sufficiently dense graphs, this gives to the first exact incremental algorithm with sub-linear amortized update time for maintaining maximum flows.

KW - data structures

KW - dynamic graph algorithms

KW - maximum flow

UR - http://www.scopus.com/inward/record.url?scp=85167351658&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2023.69

DO - 10.4230/LIPIcs.ICALP.2023.69

M3 - Contribution to proceedings

BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

A2 - Etessami, Kousha

A2 - Feige, Uriel

A2 - Puppis, Gabriele

ER -

Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Abstract

Austrian Fields of Science 2012

Keywords

Access to Document

Other files and links

Cite this