Coverability and sub-exponential parameterized algorithms in planar graphs
From MaRDI portal
Publication:4972036
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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
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
- 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?)
- (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 H-minor-free Graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Dynamic programming for graphs on surfaces
- 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
- 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 Separators
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Quickly excluding a planar graph
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Subexponential parameterized algorithm for minimum fill-in
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- The Bidimensional Theory of Bounded-Genus Graphs
Cited in
(6)- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Approximation algorithms for NP-complete problems on planar graphs
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Fast sub-exponential algorithms and compactness in planar graphs
- scientific article; zbMATH DE number 3841904 (Why is no real title available?)
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
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)
