Almost polynomial hardness of node-disjoint paths in grids

DOI10.1145/3188745.3188772zbMath1427.68021arXiv1711.01980OpenAlexW2963966355MaRDI QIDQ5230375

Rachit Nimavat, Julia Chuzhoy, David H. Kim

Publication date: 22 August 2019

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

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

zbMATH Keywords

completenessreductionsnetwork design problemscomputation network flowscomputation routing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (9)

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Towards tight(er) bounds for the excluded grid theorem ⋮ Unnamed Item ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Unnamed Item

This page was built for publication: Almost polynomial hardness of node-disjoint paths in grids