Bidimensionality and Geometric Graphs

zbMath1288.68116arXiv1107.2221MaRDI QIDQ5417643

Dimitrios M. Thilikos, Daniel Lokshtanov, Fedor V. Fomin, Saket Saurabh

Publication date: 22 May 2014

Full work available at URL: https://arxiv.org/abs/1107.2221

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (85)

On polynomial kernels for sparse integer linear programs ⋮ Compactors for parameterized counting problems ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ On the Hardness of Losing Width ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ On the Parameterized Complexity of the Expected Coverage Problem ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ On the parameterized complexity of the expected coverage problem ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ Edge-disjoint packing of stars and cycles ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Planar graph vertex partition for linear problem kernels ⋮ Unnamed Item ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Sparse obstructions for minor-covering parameters ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Finite Integer Index of Pathwidth and Treewidth ⋮ Meta-kernelization using well-structured modulators ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Unnamed Item ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ On the hardness of losing width ⋮ Unnamed Item ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Spanners in sparse graphs ⋮ Implicit branching and parameterized partial cover problems ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Explicit linear kernels for packing problems ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ A linear kernel for planar red-blue dominating set ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ A linear kernel for a planar connected dominating set ⋮ FPT algorithms for connected feedback vertex set ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Kernels for packing and covering problems ⋮ Contraction obstructions for treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Unnamed Item ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Bidimensionality and Kernels ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Bidimensionality and Geometric Graphs