On Approximating Node-Disjoint Paths in Grids

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.187zbMath1375.68090OpenAlexW2295563127MaRDI QIDQ5351898

David H. Kim, Julia Chuzhoy

Publication date: 31 August 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5303/pdf/13.pdf/

zbMATH Keywords

approximation algorithmsroutingnode-disjoint pathslayout

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (6)

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Unnamed Item ⋮ A note on solving the fleet quickest routing problem on a grid graph ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

This page was built for publication: On Approximating Node-Disjoint Paths in Grids