scientific article; zbMATH DE number 7375965

DOI10.4230/LIPIcs.ICALP.2018.38zbMath1499.68263arXiv1805.09956MaRDI QIDQ5002709

Julia Chuzhoy, David H. Kim, Rachit Nimavat

Publication date: 28 July 2021

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmsroutingnode-disjoint pathslayout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Graph minors. VII: Disjoint paths on a surface
• Approximations for the disjoint paths problem in high-diameter planar networks
• Approximating disjoint-path problems using packing integer programs
• Graph minors. XIII: The disjoint paths problem
• Routing in Undirected Graphs with Constant Congestion
• An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Logarithmic hardness of the undirected edge-disjoint paths problem
• Multicommodity flow, well-linked terminals, and routing problems
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Permutation layout
• New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
• Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout
• New hardness results for routing on disjoint paths
• On Approximating Node-Disjoint Paths in Grids
• Improved approximation for node-disjoint paths in planar graphs
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
• Edge Disjoint Paths in Moderately Connected Graphs

This page was built for publication: