Strongly polynomial dual simplex methods for the maximum flow problem

DOI10.1007/BF01582129MaRDI QIDQ1380934zbMATH OpenFDO

Authors Ronald D. Armstrong, Wei Chen, Donald Goldfarb, Zhiying Jin

Publication date 11 March 1998

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

zbMATH Keywords

maximum flow problemstrongly polynomialpreflowdual network simplex algorithmsvalid distance labels

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• 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 new strongly polynomial dual network simplex algorithm
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time

Cites work

• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A new approach to the maximum-flow problem
• 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
• Polynomial dual network simplex algorithms
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Cited in

(13)

• A strongly polynomial algorithm for the minimum maximum flow degree problem
• A new strongly polynomial dual network simplex algorithm
• Resource allocation decisions under various demands and cost requirements in an unreliable flow network
• Strongly polynomial Pivot algorithms for maximal flow problems
• Maximum flow problem in wireless ad hoc networks with directional antennas
• An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems
• A polynomial-time simplex method for the maximum \(k\)-flow problem
• On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds
• A strongly polynomial algorithm for generalized flow maximization
• Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems
• A dual graph algorithm model and its implementation of the maximum flow on the large-scale networks
• Equivalence of the primal and dual simplex algorithms 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

This page was built for publication: Strongly polynomial dual simplex methods for the maximum flow problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380934)