On strongly polynomial dual simplex algorithms for the maximum flow problem

DOI10.1007/BF02614368zbMATH Open0889.90063MaRDI QIDQ1373745FDOQ1373745

Authors: Donald Goldfarb, Wei Chen 

Publication date: 11 June 1998

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

Recommendations

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

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)

Cites Work

• Network flows. Theory, algorithms, and applications.
• A new approach to the maximum-flow problem
• A Fast Parametric Maximum Flow Algorithm and Applications
• On strongly polynomial variants of the networks simplex algorithm 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
• Title not available (Why is that?)
• An efficient implementation of the network simplex method
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Cited In (10)

• Title not available (Why is that?)
• A strongly polynomial algorithm for generalized flow maximization
• Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A polynomial-time simplex method for the maximum \(k\)-flow problem
• Strongly polynomial Pivot algorithms for maximal flow problems
• Polynomial dual network simplex algorithms
• Title not available (Why is that?)
• A new strongly polynomial dual network simplex algorithm
• An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems

This page was built for publication: On strongly polynomial 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 Q1373745)