Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
From MaRDI portal
Publication:2933640
Recommendations
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Tight kernel bounds for problems on graphs with small degeneracy
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
Cited in
(45)- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- A faster parameterized algorithm for pseudoforest deletion
- Approximation in (poly-) logarithmic space
- Twin-width and polynomial kernels
- On the parameterized complexity of the expected coverage problem
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Partially Polynomial Kernels for Set Cover and Test Cover
- Lossy kernels for connected dominating set on sparse graphs
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Tight kernel bounds for problems on graphs with small degeneracy
- Kernels for (connected) dominating set on graphs with excluded topological minors
- Independent dominating set problem revisited
- On the Parameterized Complexity of the Expected Coverage Problem
- Exploiting c-closure in kernelization algorithms for graph problems
- Approximation in (Poly-) Logarithmic Space
- scientific article; zbMATH DE number 7559412 (Why is no real title available?)
- Algorithmic properties of sparse digraphs
- Domination above \(r\)-independence: does sparseness help?
- Lossy Kernels for Hitting Subgraphs
- Lossy kernels for connected dominating set on sparse graphs
- Parameterized complexity of directed Steiner tree on sparse graphs
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- On three polynomial kernels of sequences for arbitrarily partitionable graphs
- scientific article; zbMATH DE number 7765378 (Why is no real title available?)
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Essentially tight kernels for (weakly) closed graphs
- Computing dense and sparse subgraphs of weakly closed graphs
- Twin-width and polynomial kernels
- On finding short reconfiguration sequences between independent sets
- (Independent) Roman domination parameterized by distance to cluster
- Parameterized covering in semi-ladder-free hypergraphs
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Parameterized complexity of dominating set variants in almost cluster and split graphs
- Parameterized complexity of paired domination
- Hypergraph dualization with \textsf{FPT}-delay parameterized by the degeneracy and dimension
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
- Parameterized complexity of generalizations of edge dominating set
This page was built for publication: Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933640)
