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)

zbMATH Keywords

maximum flowprimal and dual simplex algorithms

Mathematics Subject Classification ID

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

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)

• An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems
• A primal simplex variant for the maximum-flow problem
• 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

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)