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

DOI10.1016/S0167-6377(96)00052-1zbMATH Open0882.90035MaRDI QIDQ1362513FDOQ1362513

Authors: Ravindra K. Ahuja, James B. Orlin 

Publication date: 5 August 1997

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

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

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)

Cites Work

• 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
• 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

Cited In (4)

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