2026-07-22T21:35:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14183 2024-03-06T10:53:41Z ddc:004 open_access

Deterministic Maximum Flows in Simple Graphs Zhang, Tianyi graph algorithms maximum flows dynamic data structures 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tianyi Zhang 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.114 urn:nbn:de:0030-drops-141832 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.114 eng https://creativecommons.org/licenses/by/4.0/legalcode