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

DOI10.1287/MOOR.22.4.793zbMATH Open0892.90064OpenAlexW2118504961MaRDI QIDQ4385161FDOQ4385161

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

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

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)

Cited In (10)

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

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)