An Improved Kernel for Planar Connected Dominating Set
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
In this paper, we study the Planar Connected Dominating Set problem, which, given a planar graph G = (V,E) and a non-negative integer k, asks for a subset D V with |D| k such that D forms a dominating set of G and induces a connected graph. Answering an open question by S. Saurabh [The 2nd Workshop on Kernelization (WorKer 2010)], we provide a kernelization algorithm for this problem leading to a problem kernel with 130k vertices, significantly improving the previously best upper bound on the kernel size. To this end, we incorporate a vertex coloring technique with data reduction rules and introduce for the first time a distinction of two types of regions into the region decomposition framework, which allows a refined analysis of the region size and could be used to reduce the kernel sizes achieved by the region decomposition technique for a large range of problems. 2011 Springer-Verlag.
name of conference
Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings