Maximum Flow
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
Step Chart
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 |