An Improved Kernel for Planar Connected Dominating Set
| Autor: | Jianer Chen, Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783642208768 TAMC |
| DOI: | 10.1007/978-3-642-20877-5_8 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|