Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
From MaRDI portal
Publication:7356316
Cites work
- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
- A tight lower bound for planar multiway cut with fixed number of terminals
- Approximating disjoint-path problems using packing integer programs
- Approximations for the disjoint paths problem in high-diameter planar networks
- Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
- Digraphs
- Directed tree-width
- Edge-disjoint paths in planar graphs
- Edge-disjoint paths in planar graphs with constant congestion
- Fundamentals of parameterized complexity
- Graph minors. XIII: The disjoint paths problem
- scientific article; zbMATH DE number 5899246 (Why is no real title available?)
- Improved approximation for node-disjoint paths in planar graphs
- Latin 2024: theoretical informatics. 16th Latin American symposium, Puerto Varas, Chile, March 18--22, 2024. Proceedings. Part II
- Minor containment and disjoint paths in almost-linear time
- New hardness results for routing on disjoint paths
- On routing disjoint paths in bounded treewidth graphs
- On the complexity of k-SAT
- Parameterized algorithms
- Parameterized tractability of edge-disjoint paths on directed acyclic graphs
- Pre-reduction graph products: hardnesses of properly learning DFAs and approximating EDP on DAGs
- Routing with congestion in acyclic digraphs
- The directed subgraph homeomorphism problem
- The disjoint paths problem in quadratic time
- The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable
- Which problems have strongly exponential complexity?
This page was built for publication: Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7356316)
