Linear kernels for (connected) dominating set on H-minor-free graphs

No abstract is available for this paper.

• Publication year

  2012

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2012-01-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973099.7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Tight Bounds for Linkages in Planar Graphs

  2011cited by this paper
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

  2011cited by this paper
• A simpler algorithm and shorter proof for the graph minor decomposition

  2011cited by this paper
• Contraction obstructions for treewidth

  2011cited by this paper
• Odd cycle packing

  2010cited by this paper
• Kernelization hardness of connectivity problems in d-degenerate graphs

  2010cited by this paper
• Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs

  2010cited by this paper
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

  2010cited by this paper
• Bidimensionality and kernels

  2010cited by this paper
• Deciding First-Order Properties for Sparse Graphs

  2010cited by this paper
• Bidimensionality and EPTAS

  2010cited by this paper
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

  2009cited by this paper
• Domination Problems in Nowhere-Dense Classes

  2009cited by this paper
• On problems without polynomial kernels

  2009cited by this paper
• (Meta) Kernelization

  2009influential reference
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs

  2009cited by this paper
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

  2009cited by this paper
• Contraction Bidimensionality: the Accurate Picture

  2009cited by this paper
• Induced Packing of Odd Cycles in a Planar Graph

  2009cited by this paper
• Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor

  2009cited by this paper
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

  2009cited by this paper
• Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

  2008cited by this paper
• Spanners in sparse graphs

  2008cited by this paper
• The Bidimensionality Theory and Its Algorithmic Applications

  2008cited by this paper
• The Induced Disjoint Paths Problem

  2008cited by this paper
• Invitation to fixed-parameter algorithms

  2007cited by this paper
• Locally Excluding a Minor

  2007cited by this paper
• Fourier meets möbius: fast subset convolution

  2006cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)

  2006cited by this paper
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

  2005cited by this paper
• Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs

  2005cited by this paper
• Algorithmic graph minor theory: Decomposition, approximation, and coloring

  2005cited by this paper
• Improved approximation algorithms for minimum-weight vertex separators

  2005cited by this paper
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

  2005cited by this paper
• Bidimensionality: new connections between FPT algorithms and PTASs

  2005influential reference
• Grad and classes with bounded expansion II. Algorithmic aspects

  2005cited by this paper
• Dominating sets in planar graphs: branch-width and exponential speed-up

  2003cited by this paper
• Graph Minors. XVI. Excluding a non-planar graph

  2003cited by this paper
• Polynomial-time data reduction for dominating set

  2002cited by this paper
• Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

  2002cited by this paper
• Local Tree-Width, Excluded Minors, and Approximation Algorithms

  2000cited by this paper
• Fundamentals of domination in graphs

  1998cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Graph Minors: XV. Giant Steps

  1996cited by this paper
• Graph Minors .XIII. The Disjoint Paths Problem

  1995cited by this paper
• Treewidth

  1994cited by this paper
• Proceedings of the fourth annual ACM-SIAM symposium on Discrete algorithms

  1993cited by this paper
• A separator theorem for nonplanar graphs

  1990cited by this paper

• Dominating Set Knapsack: Profit Optimization on Dominating Sets

  2025cites this paper
• Engineering Dominating Patterns: A Fine-grained Case Study

  2025cites this paper
• Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs

  2024cites this paper
• Sidestepping Barriers for Dominating Set in Parameterized Complexity

  2023cites this paper
• Computing paths of large rank in planar frameworks deterministically

  2023cites this paper
• Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs

  2023cites this paper
• Combing a Linkage in an Annulus

  2022cites this paper
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

  2022cites this paper
• A general kernelization technique for domination and independence problems in sparse classes

  2020cites this paper
• Finding irrelevant vertices in linear time on bounded-genus graphs

  2019cites this paper
• Domination above r-independence: does sparseness help?

  2019cites this paper
• Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs

  2019cites this paper
• Planar Disjoint Paths in Linear Time 1

  2019cites this paper
• Some Contributions to Parameterized Complexity

  2018cites this paper
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs

  2018cites this paper
• Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs

  2018cites this paper
• Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors

  2018cites this paper
• Being Even Slightly Shallow Makes Life Hard

  2017cites this paper
• Lossy Kernels for Connected Dominating Set on Sparse Graphs

  2017cites this paper
• Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes

  2017cites this paper
• Algorithmic Properties of Sparse Digraphs

  2017cites this paper
• Deposited in DRO : 04 January 2017 Version of attached

  2017cites this paper
• Deposited in DRO : 02 December 2016 Version of attached le : Accepted Version Peer-review status of attached

  2017cites this paper
• Neighborhood complexity and kernelization for nowhere dense classes of graphs

  2016cites this paper
• Structural sparsity

  2016cites this paper
• Structural sparseness and complex networks

  2016cites this paper
• Kernelization and Sparseness : the case of Dominating Set ∗ P̊al

  2016cites this paper
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes

  2016cites this paper
• Characterising Bounded Expansion by Neighbourhood Complexity

  2016cites this paper
• Parameterized Algorithms

  2015cites this paper
• Editing to a planar graph of given degrees

  2015cites this paper
• Computer Science -- Theory and Applications

  2015influential citation
• Bidimensionality and Parameterized Algorithms (Invited Talk)

  2015cites this paper
• Recent developments in kernelization: A survey

  2014cites this paper
• Kernelization and Sparseness: the case of Dominating Set

  2014cites this paper
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

  2013cites this paper
• Tournaments and Optimality: New Results in Parameterized Complexity

  2013cites this paper
• Aspects of preprocessing applied to combinatorial graph problems

  2013cites this paper
• The Multivariate Algorithmic Revolution and Beyond

  2012influential citation
• Fixed-Parameter Tractability of Treewidth and Pathwidth

  2012cites this paper
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions

  2012cites this paper
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

  2012cites this paper
• Linear Kernels on Graphs Excluding Topological Minors

  2012cites this paper
• A linear kernel for planar total dominating set

  2012cites this paper
• Graph Minors and Parameterized Algorithm Design

  2012cites this paper
• Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs

  2012cites this paper
• Bidimensionality and kernels

  2010cites this paper
• Kernelization hardness of connectivity problems in d-degenerate graphs

  2010cites this paper