Networks · 2023 · 21 citations · 44 references
Natural SciencesMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationDiscrete OptimizationGraph AlgorithmsNetwork Flow AlgorithmsNetwork FlowsNetwork OptimizationExact AlgorithmsMaximum FlowMaximum Flow AlgorithmsMaximum Flow ProblemsMinimum Cost FlowMinimum-cost Flow AlgorithmsMinimum-cost Flow ProblemNetwork Flow Problems
Abstract Network flow problems form an important and much‐studied family of combinatorial optimization problems, with a huge array of practical applications. Two network flow problems in particular have received a great deal of attention: the maximum flow and minimum‐cost flow problems. We review the progress that has been made on exact solution algorithms for these two problems, with an emphasis on worst‐case running times.
44
Maximal Flow Through a Network
L. R. Ford, D. R. Fulkerson · Canadian Journal of Mathematics · 1956 · 2.3K citations · Full text
A new approach to the maximum-flow problem
Andrew V. Goldberg, Robert E. Tarjan · Journal of the ACM · 1988 · 1.9K citations · Full text
Beyond the flow decomposition barrier
Andrew V. Goldberg, Satish Rao · Journal of the ACM · 1998 · 474 citations · Full text