Equivalence of the primal and dual simplex algorithms for the maximum flow problem

DOI10.1016/S0167-6377(96)00052-1MaRDI QIDQ1362513zbMATH OpenFDO

Authors Ravindra K. Ahuja, James B. Orlin

Publication date 5 August 1997

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

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

zbMATH Keywords

maximum flowprimal and dual simplex algorithms

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time
• Strongly polynomial dual simplex methods for the maximum flow problem
• On strongly polynomial dual simplex algorithms for the maximum flow problem
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• A primal simplex variant for the maximum-flow problem

Cites work

• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time
• Network flows. Theory, algorithms, and applications.
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• Strongly polynomial dual simplex methods for the maximum flow problem
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Cited in

(4)

• On the equivalence of the maximum balanced flow problem and the weighted minimax flow problem
• On the transformation mechanism for formulating a multiproduct two-layer supply chain network design problem as a network flow model
• A primal simplex variant for the maximum-flow problem
• An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems

This page was built for publication: Equivalence of the primal and dual simplex algorithms for the maximum flow problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362513)