René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, and Mathias Weller. Linear-time computation of a linear problem kernel for dominating set on planar graphs. In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC'11), Saarbrücken, Germany, volume 7112 of Lecture Notes in Computer Science, pages 194–206. Springer, 2012.

We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G' of size O(γ(G)) with γ(G) = γ(G'). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G'. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.

bib | DOI | slides | .pdf ] Back


This file was generated by bibtex2html 1.98.