Multicommodity flow, well-linked terminals, and routing problems

DOI10.1145/1060590.1060618zbMath1192.90017OpenAlexW1999867351MaRDI QIDQ3581391

F. Bruce Shepherd, Chandra Chekuri, Sanjeev Khanna

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060618

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (20)

A note on multiflows and treewidth ⋮ Minimum-Cost Network Design with (Dis)economies of Scale ⋮ Constant Congestion Brambles in Directed Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ The disjoint paths problem in quadratic time ⋮ Unnamed Item ⋮ Euclidean prize-collecting Steiner forest ⋮ Routing multi-class traffic flows in the plane ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Disjoint paths in sparse graphs ⋮ Unnamed Item ⋮ Routing with congestion in acyclic digraphs ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Planar Digraphs ⋮ Unnamed Item

This page was built for publication: Multicommodity flow, well-linked terminals, and routing problems