Coverability and sub-exponential parameterized algorithms in planar graphs
From MaRDI portal
(Redirected from Publication:4972036)
Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Recommendations
- Fast sub-exponential algorithms and compactness in planar graphs
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs
Cites work
- (Meta) kernelization
- A c^k n 5-approximation algorithm for treewidth
- Algorithms – ESA 2005
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Bidimensional Parameters and Local Treewidth
- Bidimensionality and kernels
- Bidimensionality and parameterized algorithms (invited talk)
- Bidimensionality of geometric intersection graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Branchwidth of graphic matroids
- Call routing and the ratcatcher
- Contraction Bidimensionality: The Accurate Picture
- Contraction obstructions for treewidth
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Dynamic Programming and Fast Matrix Multiplication
- Dynamic programming for graphs on surfaces
- Dynamic Programming for H-minor-free Graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Fast FAST
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Faster approximation schemes and parameterized algorithms on H-minor-free and odd-minor-free graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Genus characterizes the complexity of certain graph problems: Some tight results
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 1953093 (Why is no real title available?)
- scientific article; zbMATH DE number 1953101 (Why is no real title available?)
- scientific article; zbMATH DE number 1929955 (Why is no real title available?)
- scientific article; zbMATH DE number 6783430 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- scientific article; zbMATH DE number 3236772 (Why is no real title available?)
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Linearity of grid minors in treewidth with applications through bidimensionality
- Lower bounds based on the exponential time hypothesis
- Mathematical Foundations of Computer Science 2004
- New upper bounds on the decomposability of planar graphs
- On the existence of subexponential parameterized algorithms
- Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Planar Separators
- Quickly excluding a planar graph
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Subexponential parameterized algorithm for minimum fill-in
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- 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 Bidimensional Theory of Bounded-Genus Graphs
Cited in
(7)- Fast sub-exponential algorithms and compactness in planar graphs
- scientific article; zbMATH DE number 3841904 (Why is no real title available?)
- Approximation algorithms for NP-complete problems on planar graphs
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Approximating branchwidth on parametric extensions of planarity
This page was built for publication: Coverability and sub-exponential parameterized algorithms in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972036)
