A strongly polynomial contraction-expansion algorithm for network flow problems

DOI10.1016/j.cor.2017.02.019zbMath1391.90113OpenAlexW2594925297MaRDI QIDQ1652310

Marco E. Lübbecke, Jean Bertrand Gauthier, Jacques Desrosiers

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.02.019

zbMATH Keywords

network flow problemcomplexity analysisstrongly polynomial algorithmresidual networkcontracted networkminimum mean cost cycle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (3)

Two-stage matching-and-scheduling algorithm for real-time private parking-sharing programs ⋮ Vector Space Decomposition for Solving Large-Scale Linear Programs ⋮ The minimum mean cycle-canceling algorithm for linear programs

Uses Software

• DIMACS

Cites Work

• About the minimum mean cycle-canceling algorithm
• A characterization of the minimum cycle mean in a digraph
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• Minimum-cost flow algorithms: an experimental evaluation
• Finding minimum-cost circulations by canceling negative cycles
• Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
• Linear Programming
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: A strongly polynomial contraction-expansion algorithm for network flow problems