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.