Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
From MaRDI portal
Publication:5042453
DOI10.1007/978-3-030-42071-0_9OpenAlexW3019651069MaRDI QIDQ5042453
Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Publication date: 19 October 2022
Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.08373
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Local search: is brute-force avoidable?
- Faster parameterized algorithms for minor containment
- Explicit bounds for graph minors
- Chordal deletion is fixed-parameter tractable
- Rooted routing in the plane
- Fast minor testing in planar graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Graph minors. XIII: The disjoint paths problem
- Obtaining planarity by contracting few edges
- The role of planarity in connectivity problems parameterized by treewidth
- Über eine Eigenschaft der ebenen Komplexe
- People, Problems, and Proofs
- A shorter proof of the graph minor algorithm
- The Birth and Early Years of Parameterized Complexity
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Tight Bounds for Linkages in Planar Graphs
- (Meta) Kernelization
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- On the Computational Complexity of Combinatorial Problems
- Distributed algorithms for computing shortest pairs of disjoint paths
- Finding k Disjoint Paths in a Directed Planar Graph
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- New hardness results for routing on disjoint paths
- An exponential time parameterized algorithm for planar disjoint paths
- Almost polynomial hardness of node-disjoint paths in grids
- Polynomial bounds for the grid-minor theorem
- On Approximating Node-Disjoint Paths in Grids
- Improved approximation for node-disjoint paths in planar graphs
- Improved Bounds for the Flat Wall Theorem
- Bidimensionality and Geometric Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
- Finding topological subgraphs is fixed-parameter tractable
- Parameterized Algorithms
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
- Slightly Superexponential Parameterized Problems
- The NP-completeness column: An ongoing guide
