Difference between revisions of "Maximum Flow"

From Algorithm Wiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
== Problem Description==
== Problem Description==
maximum flow problems involve finding a feasible flow through a flow network that is maximum.
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem.


== Bounds Chart ==
== Bounds Chart ==
Line 21: Line 21:
|-
|-
| rowspan="1" | Cubic
| rowspan="1" | Cubic
|
| [ Dantzig (1951)]
[https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Dinitz (1970)]
[https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549 Dinitz (1973)]
[https://www.sciencedirect.com/science/article/abs/pii/S037722179600269X Cherkassky (1977)]
[http://alexander-karzanov.net/Publications/maxflow-acyc.pdf Karzanov (1974)]
[https://link.springer.com/article/10.1007/BF00264254 Galil & Naamad (1980)]
[https://www.sciencedirect.com/science/article/pii/0022000083900065 Sleator & Tarjan (1983)][https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20new%20approach.pdf Goldberg & Tarjan (1986)][https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem Ahuja & Orlin (1987)]
[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf Ahuja et al. (1987)]
[https://ieeexplore.ieee.org/document/63465 Cheriyan & Hagerup (1989)][https://link.springer.com/chapter/10.1007/BFb0032035 Cheriyan et al. (1990)]
[ Alon (1990)]
 
|
|
|-
|-
| rowspan="1" | Quadratic
| rowspan="1" | Quadratic
|
| [http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf Ford & Fulkerson (1955)]
[https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf Edmonds & Karp (1972)]
[https://dl.acm.org/citation.cfm?id=139438 King et al. (1992)]
[https://dl.acm.org/citation.cfm?id=167201 Phillips & Westbrook (1993)]
[https://dl.acm.org/citation.cfm?id=290181 Goldberg & Rao (1997)]
[https://dl.acm.org/citation.cfm?id=290181 Goldberg & Rao (1997)]
[https://dl.acm.org/citation.cfm?id=2488705 James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm (2013)]
 
|
|
|-
|-

Latest revision as of 14:22, 23 September 2021

Problem Description

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem.

Bounds Chart

Maximum FlowBoundsChart.png

Step Chart

Maximum FlowStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic [ Dantzig (1951)]

Dinitz (1970) Dinitz (1973) Cherkassky (1977) Karzanov (1974) Galil & Naamad (1980) Sleator & Tarjan (1983)Goldberg & Tarjan (1986)Ahuja & Orlin (1987) Ahuja et al. (1987) Cheriyan & Hagerup (1989)Cheriyan et al. (1990) [ Alon (1990)]

Quadratic Ford & Fulkerson (1955)

Edmonds & Karp (1972) King et al. (1992) Phillips & Westbrook (1993) Goldberg & Rao (1997) Goldberg & Rao (1997) James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm (2013)

nlogn
Linear
logn