License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.114
URN: urn:nbn:de:0030-drops-141832
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14183/
Zhang, Tianyi
Deterministic Maximum Flows in Simple Graphs
Abstract
In this paper we are interested in deterministically computing maximum flows in undirected simple graphs where edges have unit capacities. When the input graph has n vertices and m edges, and the maximum flow is known to be upper bounded by τ as prior knowledge, our algorithm has running time Õ(m + n^{5/3}τ^{1/2}); in the extreme case where τ = Θ(n), our algorithm has running time Õ(n^{2.17}). This always improves upon the previous best deterministic upper bound Õ(n^{9/4}τ^{1/8}) by [Duan, 2013]. Furthermore, when τ ≥ n^{0.67} our algorithm is faster than a classical upper bound of O(m + nτ^{3/2}) by [Karger and Levin, 1998].
BibTeX - Entry
@InProceedings{zhang:LIPIcs.ICALP.2021.114,
author = {Zhang, Tianyi},
title = {{Deterministic Maximum Flows in Simple Graphs}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {114:1--114:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14183},
URN = {urn:nbn:de:0030-drops-141832},
doi = {10.4230/LIPIcs.ICALP.2021.114},
annote = {Keywords: graph algorithms, maximum flows, dynamic data structures}
}
|
Keywords: |
|
graph algorithms, maximum flows, dynamic data structures |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
