A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem

DOI10.1007/978-3-540-87744-8_11MaRDI QIDQ3541080zbMATH OpenOpenAlexFDO

Authors Alexander V. Karzanov, Maxim Babenko

Publication date 25 November 2008

Published in Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-87744-8_11

Mathematics Subject Classification ID

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

Recommendations

• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
• A dual descent algorithm for node-capacitated multiflow problems and its applications
• Min-cost multiflows in node-capacitated undirected networks
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• A Fast and Simple Algorithm for the Maximum Flow Problem

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 4103110 (Why is no real title available?)
• scientific article; zbMATH DE number 3550435 (Why is no real title available?)
• A Fast Algorithm for Path 2-Packing Problem
• A data structure for dynamic trees
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Beyond the flow decomposition barrier
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Matroid matching and some applications
• Minimum cost multiflows in undirected networks
• On some connectivity properties of Eulerian graphs
• Some new results on node-capacitated packing of A-paths

Cited in

(7)

• A capacity scaling algorithm for the constrained maximum flow problem
• Discrete convex functions on graphs and their algorithmic applications
• A fast algorithm for the path 2-packing problem
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• A dual descent algorithm for node-capacitated multiflow problems and its applications
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

This page was built for publication: A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem

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