Integer Maximum Flow: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 14: | Line 14: | ||
== Parameters == | == Parameters == | ||
V: number of vertices | $V$: number of vertices | ||
E: number of edges | $E$: number of edges | ||
U: maximum edge capacity | $U$: maximum edge capacity | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 32: | Line 32: | ||
| [[Dinitz ( Maximum Flow)|Dinitz]] || 1970 || $O(V^{2}E)$ || $O(E)$ || Exact || Deterministic || [https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | | [[Dinitz ( Maximum Flow)|Dinitz]] || 1970 || $O(V^{2}E)$ || $O(E)$ || Exact || Deterministic || [https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Edmonds & Karp ( Maximum Flow)|Edmonds & Karp]] || 1972 || $O(E^{2} | | [[Edmonds & Karp ( Maximum Flow)|Edmonds & Karp]] || 1972 || $O(E^{2} \log U)$ || $O(E)$ || Exact || Deterministic || [https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Karzanov ( Maximum Flow)|Karzanov]] || 1974 || $O(V^{3})$ || $O(V^{2})$ || Exact || Deterministic || [http://alexander-karzanov.net/Publications/maxflow-acyc.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | | [[Karzanov ( Maximum Flow)|Karzanov]] || 1974 || $O(V^{3})$ || $O(V^{2})$ || Exact || Deterministic || [http://alexander-karzanov.net/Publications/maxflow-acyc.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Galil & Naamad ( Maximum Flow)|Galil & Naamad]] || 1980 || $O( | | [[Galil & Naamad ( Maximum Flow)|Galil & Naamad]] || 1980 || $O(VE \log^{2} V)$ || $O(E)$ || Exact || Deterministic || [https://core.ac.uk/download/pdf/81946904.pdf Time & Space] | ||
|- | |- | ||
| [[Dantzig ( Maximum Flow)|Dantzig]] || 1951 || $O(V^{2}EU)$ || $O(VE)$? || Exact || Deterministic || | | [[Dantzig ( Maximum Flow)|Dantzig]] || 1951 || $O(V^{2}EU)$ || $O(VE)$? || Exact || Deterministic || | ||
|- | |- | ||
| [[Dinitz (with dynamic trees) ( Maximum Flow)|Dinitz (with dynamic trees)]] || 1973 || $O( | | [[Dinitz (with dynamic trees) ( Maximum Flow)|Dinitz (with dynamic trees)]] || 1973 || $O(VE \log U)$ || $O(E)$ || Exact || Deterministic || [https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Time] | ||
|- | |- | ||
| [[Cherkassky ( Maximum Flow)|Cherkassky]] || 1977 || $O(V^{2}E^{0.5})$ || $O(E)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/abs/pii/S037722179600269X Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | | [[Cherkassky ( Maximum Flow)|Cherkassky]] || 1977 || $O(V^{2}E^{0.5})$ || $O(E)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/abs/pii/S037722179600269X Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space] | ||
|- | |- | ||
| [[Sleator & Tarjan ( Maximum Flow)|Sleator & Tarjan]] || 1983 || $O( | | [[Sleator & Tarjan ( Maximum Flow)|Sleator & Tarjan]] || 1983 || $O(VE \log V)$ || $O(E)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/0022000083900065 Time] | ||
|- | |- | ||
| [[Goldberg & Tarjan ( Maximum Flow)|Goldberg & Tarjan]] || 1986 || $O( | | [[Goldberg & Tarjan ( Maximum Flow)|Goldberg & Tarjan]] || 1986 || $O(VE \log (V^{2}/E))$ || $O(E)$ || Exact || Deterministic || [https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20new%20approach.pdf Time] | ||
|- | |- | ||
| [[Ahuja & Orlin ( Maximum Flow)|Ahuja & Orlin]] || 1987 || $O(VE + V^{2} | | [[Ahuja & Orlin ( Maximum Flow)|Ahuja & Orlin]] || 1987 || $O(VE + V^{2} \log U)$ || $O(ELogU)$ || Exact || Deterministic || [https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem Time] | ||
|- | |- | ||
| [[Goldberg & Rao (Integer Maximum Flow Maximum Flow)|Goldberg & Rao]] || 1997 || $O(E^{1.5} | | [[Goldberg & Rao (Integer Maximum Flow Maximum Flow)|Goldberg & Rao]] || 1997 || $O(E^{1.5} \log(V^{2}/E) \log U)$ || $O(V + E)$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=290181 Time] | ||
|- | |- | ||
| [[Goldberg & Rao (Integer Maximum Flow Maximum Flow)|Goldberg & Rao]] || 1997 || $O(V^{0.{6}6}E | | [[Goldberg & Rao (Integer Maximum Flow Maximum Flow)|Goldberg & Rao]] || 1997 || $O(V^{0.{6}6}E \log(V^{2}/E) \log U)$ || $O(V + E)$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=290181 Time] | ||
|- | |- | ||
| [[Ahuja et al. ( Maximum Flow)|Ahuja et al.]] || 1987 || $O(VELog(V(LogU)$^{0.5} / E)) || || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf Time] | | [[Ahuja et al. ( Maximum Flow)|Ahuja et al.]] || 1987 || $O(VELog(V(LogU)$^{0.5} / E)) || || Exact || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf Time] | ||
| Line 87: | Line 87: | ||
[[File:Maximum Flow - Integer Maximum Flow - Time.png|1000px]] | [[File:Maximum Flow - Integer Maximum Flow - Time.png|1000px]] | ||
== References/Citation == | == References/Citation == | ||
https://arxiv.org/abs/2203.00671, | https://arxiv.org/abs/2203.00671, | ||
Latest revision as of 10:05, 28 April 2023
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
