Lossy Kernels for Connected Dominating Set on Sparse Graphs

DOI10.4230/LIPIcs.STACS.2018.29zbMath1487.68176arXiv1706.09339OpenAlexW2962887163MaRDI QIDQ3304128

Amer E. Mouawad, Eduard Eiben, Sebastian Siebertz, Fahad Panolan, Mithilesh Kumar

Publication date: 5 August 2020

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

zbMATH Keywords

connected dominating setsparse graph classeslossy kernelization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (11)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Lossy kernelization of same-size clustering

Cites Work

• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• A linear kernel for a planar connected dominating set
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• On nowhere dense graphs
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Domination Problems in Nowhere-Dense Classes
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• FPT Algorithms for Connected Feedback Vertex Set
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Fourier meets M\"{o}bius: fast subset convolution
• Polynomial-time data reduction for dominating set
• Graph Classes: A Survey
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
• Kernelization and Sparseness: the case of Dominating Set
• First order properties on nowhere dense structures
• Lossy kernelization
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• Parameterized Algorithms

This page was built for publication: Lossy Kernels for Connected Dominating Set on Sparse Graphs