An Improved Kernel for Planar Connected Dominating Set Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Luo, W., Wang, J., Feng, Q., Guo, J., & Chen, J.

citation count

  • 6

complete list of authors

  • Luo, Weizhong||Wang, Jianxin||Feng, Qilong||Guo, Jiong||Chen, Jianer

publication date

  • May 2011