Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Electron. Colloquium Comput. Complex.

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

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

  2006cited by this paper
• A General Data Reduction Scheme for Domination in Graphs

  2006cited by this paper
• Parameterized Complexity Theory

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

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

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

  2005cited by this paper
• Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up

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

  2003cited by this paper
• Improved Parameterized Algorithms for Planar Dominating Set

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

  2002influential reference
• The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus

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

  2002cited by this paper
• The Extremal Function for Complete Minors

  2001cited by this paper
• Refined Search Tree Technique for Dominating Set on Planar Graphs 1

  2001cited by this paper
• Proof of a Conjecture of Mader, Erdös and Hajnal on Topological Complete Subgraphs

  1998cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Topological cliques in graphs II

  1994cited by this paper
• An extremal function for contractions of graphs

  1984cited by this paper
• Lower bound of the hadwiger number of graphs by their average degree

  1984cited by this paper
• Graph Theory with Applications

  1978cited by this paper
• Graph Theory with Applications

  1977cited by this paper

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

  2023cites this paper
• Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs

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

  2020cites this paper
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs

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

  2018influential citation
• Distributed Approximation Algorithms for k-dominating Set in Graphs of Bounded Genus and Linklessly Embeddable Graphs

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

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

  2016influential citation
• Kernelization Lower Bounds Through Colors and IDs

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

  2014influential citation
• Deposited in DRO : 16 September 2014 Version of attached le : Peer-review status of attached le : Peer-reviewed Citation for published item

  2014cites this paper
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond

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

  2012cites this paper
• Parameterized Domination in Circle Graphs

  2012cites this paper
• Linear kernels for (connected) dominating set on H-minor-free graphs

  2012cites this paper
• The Kernelization complexity of some domination and covering problems

  2011influential citation
• Confronting intractability via parameters

  2011cites this paper
• A linear kernel for planar connected dominating set

  2011cites this paper
• The effect of girth on the kernelization complexity of Connected Dominating Set

  2010cites this paper
• Bidimensionality and kernels

  2010cites this paper
• Algorithms in moderately exponential time

  2010cites this paper
• New Methods in Parameterized Algorithms and Complexity

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

  2009cites this paper
• Algorithms for optimization problems on networks and graphs

  2009cites this paper
• Incompressibility through Colors and IDs

  2009cites this paper
• I  C  Id

  2009influential citation
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

  2009influential citation
• D S ] 2 9 M ar 2 00 9 Polynomial Kernels for Dominating Set in K i , j-free and d-degenerate Graphs

  2009cites this paper
• (Meta) Kernelization

  2009cites this paper
• Linear Kernel for Planar Connected Dominating Set

  2009cites this paper
• Polynomial Kernels for Dominating Set in Ki,j-free and d-degenerate Graphs

  2009influential citation
• I  C  Id

  2008cites this paper