Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem

DOI10.1287/moor.5.2.258zbMath0442.90098OpenAlexW2066087428MaRDI QIDQ3885554

Maurice Queyranne

Publication date: 1980

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://publications.polymtl.ca/5986/1/EP-R-78-43_Queyranne.pdf

zbMATH Keywords

convergence analysisnetwork flowmaximum flow problemworst case behavioraugmenting path algorithmcapacity algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items (4)

The MA-ordering max-flow algorithm is not strongly polynomial for directed networks ⋮ Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks ⋮ A maximum flow algorithm using MA ordering. ⋮ On the maximum capacity augmentation algorithm for the maximum flow problem

This page was built for publication: Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem