A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

DOI10.1145/2893472zbMath1426.68302arXiv1208.1272OpenAlexW2064656298MaRDI QIDQ3177821

Shi Li, Julia Chuzhoy

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsrouting problemsedge-disjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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: A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2