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

DOI10.1287/moor.22.4.793zbMath0892.90064OpenAlexW2118504961MaRDI QIDQ4385161

Zhiying Jin, James B. Orlin, Donald Goldfarb

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

Related Items (8)

Improving time bounds on maximum generalised flow computations by contracting the network ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ 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 ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ A new scaling algorithm for the minimum cost network flow problem ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem ⋮ Maximum network flows with concave gains

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