Difference between revisions of "Maximum Flow"

From Algorithm Wiki
Jump to navigation Jump to search
 
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 ==

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