New hardness results for routing on disjoint paths

DOI10.1145/3055399.3055411zbMath1369.68217OpenAlexW2550041253MaRDI QIDQ4977963

David H. Kim, Rachit Nimavat, Julia Chuzhoy

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsrouting problemshardness of approximationedge-disjoint pathsnode-disjoint paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ Unnamed Item ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Unnamed Item ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

This page was built for publication: New hardness results for routing on disjoint paths