Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
An Improved Kernel for Planar Connected Dominating Set
verfasst von : Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo, Jianer Chen
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 130
k
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.