A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
From MaRDI portal
Publication:6158361
DOI10.1137/21m1395089OpenAlexW3122423875MaRDI QIDQ6158361
Publication date: 31 May 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/21m1395089
planar graphsparameterized complexitydirected acyclic graphsedge-disjoint pathsexponential time hypothesis
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Irrelevant vertices for the planar disjoint paths problem
- The disjoint paths problem in quadratic time
- The directed subgraph homeomorphism problem
- Which problems have strongly exponential complexity?
- A tight lower bound for Steiner orientation
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Graph minors. XIII: The disjoint paths problem
- NP-completeness of some edge-disjoint paths problems
- A tight lower bound for planar Steiner orientation
- Routing with congestion in acyclic digraphs
- A tight lower bound for edge-disjoint paths on planar DAGs
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
- Finding k Partially Disjoint Paths in a Directed Planar Graph
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- Finding k Disjoint Paths in a Directed Planar Graph
- The limited blessing of low dimensionality
- New hardness results for routing on disjoint paths
- Coloring Graphs with Constraints on Connectivity
- An exponential time parameterized algorithm for planar disjoint paths
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- Almost polynomial hardness of node-disjoint paths in grids
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- Improved approximation for node-disjoint paths in planar graphs
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- A subexponential parameterized algorithm for Subset TSP on planar graphs
- The Graph Minor Algorithm with Parity Conditions
- Parameterized Algorithms
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- On the complexity of \(k\)-SAT
