Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost

DOI10.1287/moor.22.1.90zbMath0871.90030OpenAlexW2169798930MaRDI QIDQ4339374

Alexander V. Karzanov, Andrew V. Goldberg

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)

Related Items (7)

Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ Multiflows and disjoint paths of minimum total cost ⋮ Min-cost multiflows in node-capacitated undirected networks ⋮ Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ 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