Min-cost multiflows in node-capacitated undirected networks

DOI10.1007/s10878-011-9377-3zbMath1261.90067arXiv1001.0125MaRDI QIDQ1928531

Maxim A. Babenko, Alexander V. Karzanov

Publication date: 3 January 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.0125

zbMATH Keywords

bidirected graph; skew-symmetric graph; minimum cost multiflow

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Related Items

Faster algorithms for half-integral T -Path packing, Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polyhedra related to undirected multicommodity flows
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• Minimum cost multiflows in undirected networks
• Combinatorial optimization in geometry
• Maximum skew-symmetric flows and matchings
• Free multiflows in bidirected and skew-symmetric graphs
• Path problems in skew-symmetric graphs
• Some new results on node-capacitated packing of A-paths
• On some connectivity properties of Eulerian graphs
• Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
• Antisymmetrical Digraphs
• Chebyshev's approximation algorithms and applications