Integer Maximum Flow (Maximum Flow)
Jump to navigation
Jump to search
Description
Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities must be integers.
Related Problems
Generalizations: Non-Integer Maximum Flow
Subproblem: Unweighted Maximum Flow
Related: st-Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity
Parameters
$V$: number of vertices
$E$: number of edges
$U$: maximum edge capacity
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 |
| Goldberg & Rao | 1997 | $O(E^{1.5} \log(V^{2}/E) \log U)$ | $O(V + E)$ | Exact | Deterministic | Time |
| Goldberg & Rao | 1997 | $O(V^{0.{6}6}E \log(V^{2}/E) \log U)$ | $O(V + E)$ | 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 |
| Goldberg & Rao (Parallel) | 1997 | $O(V^{1.66} log(V)$ log(U)) | $O(V^{2})$ | Exact | Parallel | Time & Space |
| Goldberg & Rao (Parallel) | 1997 | $O(E^{0.5} V log(V)$ log(U)) | $O(V^{2})$ | Exact | Parallel | Time & Space |
Time Complexity Graph
