Improved linear problem kernel for planar connected dominating set

DOI10.1016/J.TCS.2013.06.011MaRDI QIDQ392013zbMATH OpenOpenAlexFDO

Authors Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo, Jianer Chen

Publication date 13 January 2014

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

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

zbMATH Keywords

data reductionkernelizationconnected dominating setregion decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• An improved kernel for planar connected dominating set
• Connectivity is not a limit for kernelization: planar connected dominating set
• Linear Kernel for Planar Connected Dominating Set
• A linear kernel for a planar connected dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• (Meta) Kernelization
• A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• A linear kernel for a planar connected dominating set
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• An improved kernel for planar connected dominating set
• Connectivity is not a limit for kernelization: planar connected dominating set
• Kernelization: new upper and lower bound techniques
• Linear Kernel for Planar Connected Dominating Set
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set

Cited in

(14)

• Planar graph vertex partition for linear problem kernels
• A linear kernel for a planar connected dominating set
• Connectivity is not a limit for kernelization: planar connected dominating set
• Computational study for planar connected dominating set problem
• Simpler linear-time kernelization for planar dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Improved parameterized algorithms and kernels for mixed domination
• A \(13k\)-kernel for planar feedback vertex set via region decomposition
• Linear Kernel for Planar Connected Dominating Set
• A linear kernel for planar red-blue dominating set
• An improved kernel for planar connected dominating set
• New analysis and computational study for the planar connected dominating set problem
• Improved kernel results for some FPT problems based on simple observations
• Linear problem kernels for planar graph problems with small distance property

This page was built for publication: Improved linear problem kernel for planar connected dominating set

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