Maximum Flow

From Algorithm Wiki
Revision as of 14:22, 23 September 2021 by Yashsherry (talk | contribs) (→‎Problem Description)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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