## 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.*