A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem

DOI10.1007/978-3-540-87744-8_11zbMath1158.90318OpenAlexW1543005377MaRDI QIDQ3541080

Alexander V. Karzanov, Maxim A. 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)

Related Items

Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, A fast algorithm for the path 2-packing problem, Discrete Convex Functions on Graphs and Their Algorithmic Applications, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

Cites Work

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