On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds

DOI10.1080/02331934.2013.800515zbMath1291.90332OpenAlexW1995283957MaRDI QIDQ5413870

Richárd Molnár-Szipai, Tibor Illés

Publication date: 2 May 2014

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331934.2013.800515

zbMATH Keywords

network flowspivot algorithmmaximum flow problemMBU algorithm

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) Graph algorithms (graph-theoretic aspects) (05C85) Extreme-point and pivoting methods (90C49) Flows in graphs (05C21)

Related Items (2)

Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems ⋮ Exterior point simplex-type algorithms for linear and network optimization problems

Cites Work

• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Improved Time Bounds for the Maximum Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems

This page was built for publication: On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds