A linear kernel for a planar connected dominating set

DOI10.1016/J.TCS.2010.10.045MaRDI QIDQ534569zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Matthias Mnich, Saket Saurabh

Publication date 18 May 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.10.045

zbMATH Keywords

planar graphskernelizationconnected dominating setreduce or refine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Recommendations

• Linear Kernel for Planar Connected Dominating Set
• Connectivity is not a limit for kernelization: planar connected dominating set
• Improved linear problem kernel for planar connected dominating set
• An improved kernel for planar connected dominating set
• scientific article; zbMATH DE number 2089218

Cites work

• (Meta) Kernelization
• A Linear Kernel for Planar Feedback Vertex Set
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• A quadratic kernel for feedback vertex set
• Approximation algorithms for connected dominating sets
• Bidimensionality and kernels
• Bidimensionality: new connections between FPT algorithms and PTASs
• Connectivity is not a limit for kernelization: planar connected dominating set
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
• Polynomial-time data reduction for dominating set
• Solving connected dominating set faster than \(2^n\)
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Vertex cover: Further observations and further improvements
• `` Strong NP-Completeness Results

Cited in

(18)

• An improved kernel for planar connected dominating set
• Polynomial-time data reduction for dominating set
• Lossy kernels for connected dominating set on sparse graphs
• Smaller kernels for several FPT problems based on simple observations
• SOFSEM 2006: Theory and Practice of Computer Science
• A linear kernel for planar total dominating set
• Lossy kernels for connected dominating set on sparse graphs
• Improved linear problem kernel for planar connected dominating set
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Kernelization and Sparseness: the case of Dominating Set
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Kernelization of packing problems
• Finding minimum weight connected dominating set in stochastic graph based on learning automata
• Connectivity is not a limit for kernelization: planar connected dominating set
• Improved kernel results for some FPT problems based on simple observations
• A linear kernel for planar red-blue dominating set
• Simpler linear-time kernelization for planar dominating set

This page was built for publication: A linear kernel for a planar connected dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534569)