Improved Time Bounds for the Maximum Flow Problem

DOI10.1137/0218065zbMath0675.90029OpenAlexW2046043928MaRDI QIDQ3830789

James B. Orlin, Ravindra K. Ahuja, Robert Endre Tarjan

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

maximum network flowAhuja-Orlin algorithmnonconstant scaling factorwave 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) Data structures (68P05) Algorithms in computer science (68W99)

Related Items (35)

On the generalized 2-peripatetic salesman problem ⋮ Computing maximum mean cuts ⋮ Sequential and parallel algorithms for minimum flows. ⋮ A generalization of the scaling max-flow algorithm ⋮ Recent developments in maximum flow algorithms ⋮ On the integral 4-packing of \(T\)-cuts ⋮ Separation, dimension, and facet algorithms for node flow polyhedra ⋮ Simple linear flow decomposition algorithms on trees, circles, and augmented trees ⋮ On implementing push-relabel method for the maximum flow problem ⋮ A fast maximum flow algorithm ⋮ Maximum skew-symmetric flows ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Search for all \(d\)-mincuts of a limited-flow network ⋮ Combinatorial optimization in geometry ⋮ Generating pseudo-random permutations and maximum flow algorithms ⋮ An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem ⋮ Use of dynamic trees in a network simplex algorithm for the maximum flow problem ⋮ Unnamed Item ⋮ Finding minimum-cost flows by double scaling ⋮ On the computational behavior of a polynomial-time network flow algorithm ⋮ Approximating the permanent of graphs with large factors ⋮ A new fixed point approach for stable networks and stable marriages ⋮ On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ A new approach for computing a most positive cut using the minimum flow algorithms ⋮ AO(nm log(U/n)) time maximum flow algorithm ⋮ More efficient parallel flow algorithms ⋮ A new algorithm for solving the feasibility problem of a network flow ⋮ Executability of scenarios in Petri nets ⋮ A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time ⋮ Computational investigations of maximum flow algorithms ⋮ A new saling algorithm for the maximum mean cut problem ⋮ Network flow and 2-satisfiability ⋮ Unnamed Item ⋮ The maximum flow problem: A max-preflow approach

This page was built for publication: Improved Time Bounds for the Maximum Flow Problem