Strongly polynomial dual simplex methods for the maximum flow problem

DOI10.1007/BF01582129zbMATH Open0894.90058MaRDI QIDQ1380934FDOQ1380934

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A new approach to 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
• Polynomial dual network simplex algorithms
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• A Fast and Simple Algorithm for the Maximum Flow Problem

Cited In (7)

• Equivalence of the primal and dual simplex algorithms for the maximum flow problem
• Maximum flow problem in wireless ad hoc networks with directional antennas
• A strongly polynomial algorithm for generalized flow maximization
• Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems
• Resource allocation decisions under various demands and cost requirements in an unreliable flow network
• 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: 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)