On strongly polynomial dual simplex algorithms for the maximum flow problem

DOI10.1007/BF02614368zbMath0889.90063MaRDI QIDQ1373745

Donald Goldfarb, Wei Chen

Publication date: 11 June 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

dual network simplex algorithmparametric maximum flow problemspreflowpseudoaugmenting path

Mathematics Subject Classification ID

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

Related Items (1)

An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems

Cites Work

• Unnamed Item
• 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
• An efficient implementation of the network simplex method
• A new approach to the maximum-flow problem
• A Fast Parametric Maximum Flow Algorithm and Applications

This page was built for publication: On strongly polynomial dual simplex algorithms for the maximum flow problem