An improved kernel for planar connected dominating set

DOI10.1007/978-3-642-20877-5_8MaRDI QIDQ3010387zbMATH OpenOpenAlexFDO

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

Publication date 1 July 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20877-5_8

Mathematics Subject Classification ID

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

Recommendations

• Improved linear problem 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?)
• (Meta) Kernelization
• 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
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set

Cited in

(10)

• A linear kernel for a planar connected dominating set
• Smaller kernels for several FPT problems based on simple observations
• Linear Kernel for Planar Connected Dominating Set
• Planar graph vertex partition for linear problem kernels
• Improved linear problem kernel for planar connected dominating set
• Linear problem kernels for planar graph problems with small distance property
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Towards optimal kernel for connected vertex cover in planar graphs
• Connectivity is not a limit for kernelization: planar connected dominating set
• A linear kernel for planar red-blue dominating set

This page was built for publication: An improved 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 Q3010387)