| 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 [email protected]?V with |D|@?k such that D forms a dominating set of G and induces a connected graph. Answering an open question posed at the 2nd Workshop on Kernelization (WorKer 2010), we provide a kernelization algorithm for this problem, leading to a problem kernel with at most 130k vertices, 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 a type distinction of regions into the region decomposition framework, which allows a refined analysis of the region size. |
Full Text from ScienceDirect