Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
From MaRDI portal
Publication:1957653
Recommendations
Cites work
- A Dynamic Programming Approach to Sequencing Problems
- A Separator Theorem for Planar Graphs
- Algorithms – ESA 2005
- Applications of a Planar Separator Theorem
- Bidimensionality: new connections between FPT algorithms and PTASs
- Call routing and the ratcatcher
- Computational Study on Dominating Set Problem of Planar Graphs
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Graph minors. X: Obstructions to tree-decomposition
- Graph separators: A parameterized view
- scientific article; zbMATH DE number 5764900 (Why is no real title available?)
- scientific article; zbMATH DE number 3898613 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1303538 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1953101 (Why is no real title available?)
- New upper bounds on the decomposability of planar graphs
- Parameterized complexity: exponential speed-up for planar graph problems
- Quickly excluding a planar graph
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
- The searching over separators strategy to solve some NP-hard problems in subexponential time
- Tour merging via branch-decomposition
Cited in
(51)- Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
- Fast minor testing in planar graphs
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- Exact algorithms for finding longest cycles in claw-free graphs
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- An improved exact algorithm for TSP in graphs of maximum degree 4
- Parameterized complexity of graph planarity with restricted cyclic orders
- Fixed-parameter tractability of treewidth and pathwidth
- Graph minors and parameterized algorithm design
- New analysis and computational study for the planar connected dominating set problem
- The parameterized complexity of local search for TSP, more refined
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Confronting intractability via parameters
- A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Surprising Applications of Treewidth Bounds for Planar Graphs
- A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Decomposition of Map Graphs with Applications.
- Subexponential parameterized algorithms for graphs of polynomial growth
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Algorithms – ESA 2005
- Dynamic programming for graphs on surfaces
- Exact distance oracles for planar graphs
- Slightly superexponential parameterized problems
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
- Parameterized complexity of graph planarity with restricted cyclic orders
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Upward book embeddability of \(st\)-graphs: complexity and algorithms
- Counting cycles on planar graphs in subexponential time
- An ETH-Tight Exact Algorithm for Euclidean TSP
- Counting cycles on planar graphs in subexponential time
- Faster parameterized algorithms for minor containment
- The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
- The role of twins in computing planar supports of hypergraphs
- Parameterized and approximation algorithms for the maximum bimodal subgraph problem
- On budget-constrained coverage in multi-interface networks: branchwidth and treewidth perspectives
- A tight subexponential-time algorithm for two-page book embedding
- Separator theorem and algorithms for planar hyperbolic graphs
- ETH-tight algorithm for cycle packing on unit disk graphs
- Structure and independence in hyperbolic uniform disk graphs
- Decomposition of map graphs with applications
- Induced packing of odd cycles in planar graphs
This page was built for publication: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1957653)
