Multicuts and integral multiflows in rings

DOI10.1016/j.ejor.2008.05.006zbMath1176.90483OpenAlexW2017870028MaRDI QIDQ1041998

Lucas Létocart, Cédric Bentz, Frédéric Roupin, Marie-Christine Costa

Publication date: 7 December 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.05.006

zbMATH Keywords

combinatorial optimizationring networksmulticutmaximum integral multiflow

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

Pairwise cooperations in selfish ring routing for minimax linear latency ⋮ Network design with a discrete set of traffic matrices ⋮ Stability vs. optimality in selfish ring routing ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Balancing Load via Small Coalitions in Selfish Ring Routing Games

Cites Work

• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Improved complexity bounds for location problems on the real line
• A greedy algorithm for multicut and integral multiflow in rooted trees
• An algorithm for node-capacitated ring routing
• Multicommodity flows in cycle graphs
• Cyclic Scheduling via Integer Programs with Circular Ones
• The Ring Loading Problem
• Linear time algorithms for the ring loading problem with demand splitting
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Multicommodity Flows in Ring Networks
• Algorithms and Data Structures

This page was built for publication: Multicuts and integral multiflows in rings