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

DOI10.1016/S0167-6377(96)00052-1zbMath0882.90035MaRDI QIDQ1362513

James B. Orlin, Ravindra K. Ahuja

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)

Related Items (2)

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

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
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• Strongly polynomial dual simplex methods for the maximum flow problem

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