An Improved Kernel for Planar Connected Dominating Set

DOI10.1007/978-3-642-20877-5_8zbMath1333.05295OpenAlexW1574527973MaRDI QIDQ3010387

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

Related Items (4)

Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Planar graph vertex partition for linear problem kernels ⋮ Improved linear problem kernel for planar connected dominating set ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles

Cites Work

• Unnamed Item
• 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
• 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: An Improved Kernel for Planar Connected Dominating Set