On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem

DOI10.1016/0167-6377(91)90039-RzbMath0754.90025OpenAlexW1990337640MaRDI QIDQ1180817

Donald Goldfarb, Jianxiu Hao

Publication date: 27 June 1992

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

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90039-r

zbMATH Keywords

network flowpotential functionnetwork simplex algorithmprimal simplex method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (8)

Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems ⋮ Equivalence of the primal and dual simplex algorithms for the maximum flow problem ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ On strongly polynomial dual simplex algorithms for the maximum flow problem ⋮ Strongly polynomial dual simplex methods for the maximum flow problem ⋮ On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds ⋮ A polynomial-time simplex method for the maximum \(k\)-flow problem ⋮ Computational investigations of maximum flow algorithms

Cites Work

• Unnamed Item
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• Fast Algorithms for Bipartite Network Flow
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A bad network problem for the simplex method and other minimum cost flow algorithms

This page was built for publication: On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem