# Unweighted Maximum Flow (Maximum Flow)

## Description

Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, all edges have unit weight.

## Related Problems

Generalizations: Integer Maximum Flow

## Parameters

$V$: number of vertices

$E$: number of edges

## Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Ford & Fulkerson 1955 $O(E^{2}U)$ $O(E)$ Exact Deterministic Time & Space
Dinitz 1970 $O(V^{2}E)$ $O(E)$ Exact Deterministic Time & Space
Edmonds & Karp 1972 $O(E^{2} \log U)$ $O(E)$ Exact Deterministic Time & Space
Karzanov 1974 $O(V^{3})$ $O(V^{2})$ Exact Deterministic Time & Space
Galil & Naamad 1980 $O(VE \log^{2} V)$ $O(E)$ Exact Deterministic Time & Space
Dantzig 1951 $O(V^{2}EU)$ $O(VE)$? Exact Deterministic
Dinitz (with dynamic trees) 1973 $O(VE \log U)$ $O(E)$ Exact Deterministic Time
Cherkassky 1977 $O(V^{2}E^{0.5})$ $O(E)$ Exact Deterministic Time & Space
Sleator & Tarjan 1983 $O(VE \log V)$ $O(E)$ Exact Deterministic Time
Goldberg & Tarjan 1986 $O(VE \log (V^{2}/E))$ $O(E)$ Exact Deterministic Time
Ahuja & Orlin 1987 $O(VE + V^{2} \log U)$ $O(ELogU)$ Exact Deterministic Time
Ahuja et al. 1987 $O(VELog(V(LogU)$^{0.5} / E)) Exact Deterministic Time
MKM Algorithm 1978 $O(V^{3})$ $O(E)$ Exact Deterministic Time & Space
Galil 1978 $O(V^({5}/{3})$E^({2}/{3})) $O(E)$ Exact Deterministic Time & Space
Shiloach 1981 $O(V^{3}*log(V)$/p) $O(E)$ Exact Parallel Time
Gabow 1985 $O(VE*logU)$ $O(E)$ Exact Deterministic Time
Lee, Sidford 2014 $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) $O(E)$ Exact Deterministic Time
Madry 2016 $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) $O(E)$ Exact Deterministic Time
Kathuria, Liu, Sidford 2020 $O(E^({1}+o({1})$)/sqrt(eps)) $O(E)$ or $O(V^{2})$ ? 1+eps Deterministic Time
Kathuria, Liu, Sidford 2020 $O(E^({4}/{3}+o({1})$)U^({1}/{3})) $O(E)$ or $O(V^{2})$ ? Exact Deterministic Time
Brand et al 2021 $O((E+V^{1.5})$log(U)polylog(V, E, log U)) $O(E)$ Exact Randomized Time
Gao, Liu, Peng 2021 $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) $O(E)$ Exact Deterministic Time
Chen et al 2022 $O(E^({1}+o({1})$)*log(U)) $O(E)$ Exact Deterministic Time