An exponential time parameterized algorithm for planar disjoint paths
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Cites work
- (Meta) kernelization
- A near-optimal planarization algorithm
- A shorter proof of the graph minor algorithm: the unique linkage theorem
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
- A simpler algorithm and shorter proof for the graph minor decomposition
- A subexponential parameterized algorithm for subset TSP on planar graphs
- Accelerated bend minimization
- Almost polynomial hardness of node-disjoint paths in grids
- Approximating connectivity domination in weighted bounded-genus graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computational Complexity
- Disjoint Paths in a Planar Graph—A General Theorem
- Excluded grid minors and efficient polynomial-time approximation schemes
- Finding k Disjoint Paths in a Directed Planar Graph
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Graphs on surfaces
- scientific article; zbMATH DE number 16298 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Improved approximation for node-disjoint paths in grids with sources on the boundary
- Improved approximation for node-disjoint paths in planar graphs
- Irrelevant vertices for the planar disjoint paths problem
- Linearity of grid minors in treewidth with applications through bidimensionality
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- New hardness results for routing on disjoint paths
- On approximating node-disjoint paths in grids
- On the Computational Complexity of Combinatorial Problems
- Polynomial bounds for the grid-minor theorem
- Quickly excluding a planar graph
- Reducibility among combinatorial problems
- Slightly superexponential parameterized problems
- Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- The directed subgraph homeomorphism problem
- The disjoint paths problem in quadratic time
- The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable
- The role of planarity in connectivity problems parameterized by treewidth
This page was built for publication: An exponential time parameterized algorithm for planar disjoint paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7006889)
