Coverability and sub-exponential parameterized algorithms in planar graphs
From MaRDI portal
Publication:4972036
zbMATH Open1425.05041MaRDI QIDQ4972036FDOQ4972036
Authors: Dimitrios M. Thilikos 
Publication date: 22 November 2019
Full work available at URL: http://bulletin.math.uoc.gr/vol/60/60-110-124.pdf
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
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)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Title not available (Why is that?)
- Call routing and the ratcatcher
- Lower bounds based on the exponential time hypothesis
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Quickly excluding a planar graph
- Bidimensionality and kernels
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- On the existence of subexponential parameterized algorithms
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
- Dynamic Programming and Fast Matrix Multiplication
- Title not available (Why is that?)
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Title not available (Why is that?)
- New upper bounds on the decomposability of planar graphs
- Fast FAST
- Contraction Bidimensionality: The Accurate Picture
- Subexponential parameterized algorithms
- Mathematical Foundations of Computer Science 2004
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Subexponential parameterized algorithm for minimum fill-in
- Planar Separators
- Contraction obstructions for treewidth
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Title not available (Why is that?)
- Branchwidth of graphic matroids
- Linearity of grid minors in treewidth with applications through bidimensionality
- Bidimensional Parameters and Local Treewidth
- Title not available (Why is that?)
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Dynamic programming for graphs on surfaces
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- The Bidimensional Theory of Bounded-Genus Graphs
- Algorithms – ESA 2005
- Faster approximation schemes and parameterized algorithms on \(H\)-minor-free and odd-minor-free graphs
- Title not available (Why is that?)
- A \(c^k n\) 5-approximation algorithm for treewidth
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- (Meta) kernelization
- Bidimensionality and parameterized algorithms (invited talk)
- Dynamic Programming for H-minor-free Graphs
- Bidimensionality of geometric intersection graphs
- Title not available (Why is that?)
- Genus characterizes the complexity of certain graph problems: Some tight results
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
Cited In (6)
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
- Title not available (Why is that?)
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Fast sub-exponential algorithms and compactness in planar graphs
- Approximation algorithms for NP-complete problems on planar graphs
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)
