An O (n 2 (m + N log n )log n ) min-cost flow algorithm

DOI10.1145/42282.214090zbMath0652.90039OpenAlexW2028009936MaRDI QIDQ3798456

Éva Tardos, Zvi Galil

Publication date: 1988

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/42282.214090

zbMATH Keywords

networkpolynomial algorithmdense graphsout-of-kilter algorithmminimum-cost circulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Deterministic network models in operations research (90B10)

Related Items

Cycle-based reducibility of multi-index transport-type systems of linear inequalities ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ The minimal average cost flow problem ⋮ Multiindex optimal production planning problems ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Three-index linear programs with nested structure ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ Multi-index transport problems with decomposition structure ⋮ Multicommodity flows in tree-like networks