Strongly polynomial dual simplex methods for the maximum flow problem

DOI10.1007/BF01582129zbMath0894.90058MaRDI QIDQ1380934

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

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) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (5)

Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems ⋮ Equivalence of the primal and dual simplex algorithms for the maximum flow problem ⋮ An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems ⋮ Maximum flow problem in wireless ad hoc networks with directional antennas ⋮ Resource allocation decisions under various demands and cost requirements in an unreliable flow network

Cites Work

• Polynomial dual network simplex algorithms
• 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
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A new approach to the maximum-flow problem
• Unnamed Item
• Unnamed Item

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