A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
Oliverio Cruz‐Mejía, Adam N. Letchford
Abstract
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.
Topics & Concepts
Minimum-cost flow problemMaximum flow problemFlow networkFlow (mathematics)Multi-commodity flow problemComputer scienceMathematical optimizationAlgorithmCombinatorial optimizationMathematicsGeometryComplexity and Algorithms in GraphsAdvanced Graph Theory ResearchVehicle Routing Optimization Methods