View source for Unweighted Maximum Flow

{{DISPLAYTITLE: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]]

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

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Ford & Fulkerson ( Maximum Flow)|Ford & Fulkerson]] || 1955 || $O(E^{2}U)$ || $O(E)$ || Exact || Deterministic || [http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf 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} \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]
|-
| [[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 ||  
|-
| [[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.ezproxy.canberra.edu.au/science/article/abs/pii/S037722179600269X Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space]
|-
| [[Sleator & Tarjan ( Maximum Flow)|Sleator & Tarjan]] || 1983 || $O(VE \log V)$ || $O(E)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0022000083900065 Time]
|-
| [[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} \log U)$ || $O(ELogU)$ || Exact || Deterministic || [https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem 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]
|-
| [[MKM Algorithm ( Maximum Flow)|MKM Algorithm]] || 1978 || $O(V^{3})$ || $O(E)$ || Exact || Deterministic || [https://eprints.utas.edu.au/160/1/iplFlow.pdf Time] & [https://core.ac.uk/download/pdf/81946904.pdf Space]
|-
| [[Galil ( Maximum Flow)|Galil]] || 1978 || $O(V^({5}/{3})$E^({2}/{3})) || $O(E)$ || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF00264254 Time & Space]
|-
| [[Shiloach ( Maximum Flow)|Shiloach]] || 1981 || $O(V^{3}*log(V)$/p) || $O(E)$ || Exact || Parallel || [http://users.umiacs.umd.edu/~vishkin/TEACHING/4CLASS/SV82-maxflow.pdf Time]
|-
| [[Gabow ( Maximum Flow)|Gabow]] || 1985 || $O(VE*logU)$ || $O(E)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/002200008590039X Time]
|-
| [[Lee, Sidford ( Maximum Flow)|Lee, Sidford]] || 2014 || $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) || $O(E)$ || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/stamp/stamp.jsp?tp=&arnumber=6979027 Time]
|-
| [[Madry ( Maximum Flow)|Madry]] || 2016 || $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) || $O(E)$ || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/stamp/stamp.jsp?tp=&arnumber=7782974 Time]
|-
| [[Kathuria, Liu, Sidford ( Maximum Flow)|Kathuria, Liu, Sidford]] || 2020 || $O(E^({1}+o({1})$)/sqrt(eps)) || $O(E)$ or $O(V^{2})$ ? || 1+eps || Deterministic || [https://epubs-siam-org.ezproxy.canberra.edu.au/doi/abs/10.1137/20M1383525 Time]
|-
| [[Kathuria, Liu, Sidford ( Maximum Flow)|Kathuria, Liu, Sidford]] || 2020 || $O(E^({4}/{3}+o({1})$)U^({1}/{3})) || $O(E)$ or $O(V^{2})$ ? || Exact || Deterministic || [https://epubs-siam-org.ezproxy.canberra.edu.au/doi/abs/10.1137/20M1383525 Time]
|-
| [[Brand et al ( Maximum Flow)|Brand et al]] || 2021 || $O((E+V^{1.5})$log(U)polylog(V, E, log U)) || $O(E)$ || Exact || Randomized || [https://arxiv.org/abs/2101.05719 Time]
|-
| [[Gao, Liu, Peng ( Maximum Flow)|Gao, Liu, Peng]] || 2021 || $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) || $O(E)$ || Exact || Deterministic || [https://arxiv.org/abs/2101.07233 Time]
|-
| [[Chen et al ( Maximum Flow)|Chen et al]] || 2022 || $O(E^({1}+o({1})$)*log(U)) || $O(E)$ || Exact || Deterministic || [https://arxiv.org/abs/2203.00671 Time]
|-
|}

== References/Citation == 

https://arxiv.org/abs/2203.00671