Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem

DOI10.1287/MOOR.22.4.793MaRDI QIDQ4385161zbMATH OpenOpenAlexFDO

Authors Donald Goldfarb, Zhiying Jin, James B. Orlin

Publication date 3 August 1998

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/2626

zbMATH Keywords

worst-case complexitiesgeneralized circulation problemhighest-gain augmenting paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 2163908
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• A polynomial dual simplex algorithm fot the generalized circulation problem.
• Generalized max flows and augmenting paths
• A Faster Combinatorial Algorithm for the Generalized Circulation Problem
• Combinatorial Algorithms for the Generalized Circulation Problem
• Fast algorithms for diameter-optimally augmenting paths
• A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem
• scientific article; zbMATH DE number 3956777
• A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Cited in

(10)

• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A new scaling algorithm for the minimum cost network flow problem
• Maximum network flows with concave gains
• Shortest path and maximum flow problems in networks with additive losses and gains
• Generalized maximum flow over time with intermediate storage
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
• A strongly polynomial algorithm for generalized flow maximization
• A polynomial dual simplex algorithm fot the generalized circulation problem.
• Improving time bounds on maximum generalised flow computations by contracting the network

This page was built for publication: Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem

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