Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost

DOI10.1287/MOOR.22.1.90MaRDI QIDQ4339374zbMATH OpenOpenAlexFDO

Authors Andrew V. Goldberg, Alexander V. Karzanov

Publication date 9 June 1997

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.22.1.90

zbMATH Keywords

undirected graphhalf-integer optimal solutionnonnegative integer-valued edge capacitiespurely combinatorial polynomial algorithms

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Recommendations

• Finding minimum-cost flows by double scaling
• A scaling algorithm for multicommodity flow problems
• A new scaling algorithm for the minimum cost network flow problem
• scientific article; zbMATH DE number 1263274
• A scaling out-of-kilter algorithm for minimum cost flow
• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
• A generalization of the scaling max-flow algorithm
• A double scaling algorithm for the constrained maximum flow problem

Cited in

(9)

• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• Discrete convex functions on graphs and their algorithmic applications
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Multiflows and disjoint paths of minimum total cost
• Minimum cost multiflows in undirected networks
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Min-cost multiflows in node-capacitated undirected networks
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

This page was built for publication: Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4339374)