Min-cost multiflows in node-capacitated undirected networks

DOI10.1007/s10878-011-9377-3zbMath1261.90067arXiv1001.0125OpenAlexW2098682065MaRDI 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 graphskew-symmetric graphminimum cost multiflow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (4)

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

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

This page was built for publication: Min-cost multiflows in node-capacitated undirected networks