scientific article; zbMATH DE number 7135331

zbMath1425.05041MaRDI QIDQ4972036

Dimitrios M. Thilikos

Publication date: 22 November 2019

Full work available at URL: http://bulletin.math.uoc.gr/vol/60/60-110-124.pdf

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

planar graphsparameterized algorithmsbranchwidthscattered setcoverable problemsradial domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Subexponential parameterized algorithms
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Linearity of grid minors in treewidth with applications through bidimensionality
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• On the existence of subexponential parameterized algorithms
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Contraction obstructions for treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The role of planarity in connectivity problems parameterized by treewidth
• Genus characterizes the complexity of certain graph problems: Some tight results
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Dynamic Programming for H-minor-free Graphs
• Bidimensionality of Geometric Intersection Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• (Meta) Kernelization
• New upper bounds on the decomposability of planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• The Bidimensional Theory of Bounded-Genus Graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
• Dynamic Programming for Graphs on Surfaces
• Fast FAST
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Contraction Bidimensionality: The Accurate Picture
• Planar Separators
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Mathematical Foundations of Computer Science 2004
• Bidimensional Parameters and Local Treewidth
• Bidimensionality and Parameterized Algorithms (Invited Talk)
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Bidimensionality and Geometric Graphs
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Dynamic Programming and Fast Matrix Multiplication
• Algorithms – ESA 2005
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

This page was built for publication: