A tight lower bound for edge-disjoint paths on planar DAGs
From MaRDI portal
Publication:2692724
DOI10.1007/978-3-030-75242-2_13OpenAlexW3160838608MaRDI QIDQ2692724
Publication date: 22 March 2023
Full work available at URL: https://arxiv.org/abs/2101.10742
Related Items (1)
Cites Work
- 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 (3 volumes)
- 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
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Finding k Partially Disjoint Paths in a Directed Planar Graph
- Finding k Disjoint Paths in a Directed Planar Graph
- The limited blessing of low dimensionality
- New hardness results for routing on disjoint paths
- 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
- Improved approximation for node-disjoint paths in planar graphs
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: A tight lower bound for edge-disjoint paths on planar DAGs
