Difference between revisions of "Maximum Flow"
Jump to navigation
Jump to search
Yashsherry (talk  contribs) 
Yashsherry (talk  contribs) 

Line 1:  Line 1:  
== Problem Description==  == Problem Description==  
maximum flow problems involve finding a feasible flow through a flow network that  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
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 