New polynomial-time cycle-canceling algorithms for minimum-cost flows

DOI<53::AID-NET6>3.0.CO;2-Y 10.1002/1097-0037(200008)36:1<53::AID-NET6>3.0.CO;2-YzbMath0969.90021OpenAlexW2061404140MaRDI QIDQ4509383

James B. Orlin, P. T. Sokkalingam, Ravindra K. Ahuja

Publication date: 4 October 2001

Full work available at URL: https://doi.org/10.1002/1097-0037(200008)36:1<53::aid-net6>3.0.co;2-y

zbMATH Keywords

network flowsstrongly polynomial algorithmsscaling algorithmsminimum-cost flow problemconvex cost-flow problemcycle-canceling algorithm

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity and performance of numerical algorithms (65Y20)

Related Items (8)

Generalized minimal cost flow problem in fuzzy nature: an application in bus network planning problem ⋮ Preemptive benchmarking problem: An approach for official statistics in small areas ⋮ A novel approach to subgraph selection with multiple weights on arcs ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ Scheduling for electricity cost in a smart grid ⋮ Combinatorial algorithms for the minimum interval cost flow problem ⋮ Solving coalitional resource games ⋮ Scheduling for Electricity Cost in Smart Grid

Cites Work

• Note on Weintraub’s Minimum-Cost Circulation Algorithm
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems

This page was built for publication: New polynomial-time cycle-canceling algorithms for minimum-cost flows