Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
From MaRDI portal
Publication:2933640
DOI10.1145/2390176.2390187zbMath1301.68164OpenAlexW2076551320MaRDI QIDQ2933640
Venkatesh Raman, Geevarghese Philip, Somnath Sikdar
Publication date: 5 December 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2390176.2390187
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (23)
On the Parameterized Complexity of the Expected Coverage Problem ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ On the parameterized complexity of the expected coverage problem ⋮ 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 ⋮ 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 ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ Unnamed Item ⋮ Independent dominating set problem revisited ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation in (Poly-) logarithmic space ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Approximation in (Poly-) Logarithmic Space ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Lossy Kernels for Hitting Subgraphs ⋮ Twin-width and polynomial kernels
This page was built for publication: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
