Linear kernel for planar connected dominating set
Publikationstyp
Conference Paper
Date Issued
2009-05
Sprache
English
TORE-URI
First published in
Number in series
5532 LNCS
Start Page
281
End Page
290
Citation
6th International Conference on Theory and Applications of Models of Computation, TAMC 2009
Contribution to Conference
Publisher DOI
Publisher
Springer
We provide polynomial time data reduction rules for Connected Dominating Set in planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful to obtain linear kernels for other problems on planar graphs.
DDC Class
004: Informatik