Improved approximation for node-disjoint paths in planar graphs

DOI10.1145/2897518.2897538zbMath1376.68170arXiv1603.05520OpenAlexW2297903070MaRDI QIDQ5361861

David H. Kim, Julia Chuzhoy, Shi Li

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsrouting problemsnode-disjoint paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

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 ⋮ 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: Improved approximation for node-disjoint paths in planar graphs