Improved linear problem kernel for planar connected dominating set

DOI10.1016/j.tcs.2013.06.011zbMath1358.05285OpenAlexW2131265093MaRDI QIDQ392013

Qilong Feng, Jianxin Wang, Weizhong Luo, Jiong Guo, Jian'er 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 reductionconnected dominating setkernelizationregion decomposition

Mathematics Subject Classification ID

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

Related Items (2)

A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Improved kernel results for some FPT problems based on simple observations

Cites Work

• Unnamed Item
• Unnamed Item
• A linear kernel for a planar connected dominating set
• An Improved Kernel for Planar Connected Dominating Set
• A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
• Polynomial-time data reduction for dominating set
• Linear Kernel for Planar Connected Dominating Set
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• Kernelization: New Upper and Lower Bound Techniques
• (Meta) Kernelization
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

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