A Fast and Simple Algorithm for the Maximum Flow Problem

DOI10.1287/OPRE.37.5.748zbMath0691.90024OpenAlexW2109567578MaRDI QIDQ3033534

James B. Orlin, Ravindra K. Ahuja

Publication date: 1989

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

Full work available at URL: http://hdl.handle.net/1721.1/47952

zbMATH Keywords

sequential algorithmparallel implementationmaximum flowinteger arc capacities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Theory of operating systems (68N25)

Related Items (29)

Sequential and parallel algorithms for minimum flows. ⋮ A generalization of the scaling max-flow algorithm ⋮ Recent developments in maximum flow algorithms ⋮ Minimum cuts in parametric networks ⋮ An auction algorithm for the max-flow problem ⋮ A fast algorithm for the minimax flow problem with 0/1 weights ⋮ Dual coordinate step methods for linear network flow problems ⋮ Strongly polynomial dual simplex methods for the maximum flow problem ⋮ Minimum cut problem using bases of extended polymatroids ⋮ A fast maximum flow algorithm ⋮ An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems ⋮ Just-in-Time Scheduling with Equal-Size Jobs ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Generating pseudo-random permutations and maximum flow algorithms ⋮ Use of dynamic trees in a network simplex algorithm for the maximum flow problem ⋮ Processor-efficient implementation of a maximum flow algorithm ⋮ Finding minimum-cost flows by double scaling ⋮ A new Karzanov-type \(O(n^ 3)\) max-flow algorithm ⋮ On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds ⋮ Auction algorithms for network flow problems: A tutorial introduction ⋮ Due dates assignment and JIT scheduling with equal-size jobs ⋮ AO(nm log(U/n)) time maximum flow algorithm ⋮ Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\) ⋮ Computational investigations of maximum flow algorithms ⋮ Capacity expansion and reliability evaluation on the networks flows with continuous stochastic functional capacity ⋮ An algorithmic study of the maximum flow problem: A comparative statistical analysis ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ A new saling algorithm for the maximum mean cut problem ⋮ The maximum flow problem: A max-preflow approach

This page was built for publication: A Fast and Simple Algorithm for the Maximum Flow Problem