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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- (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
- 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)
