Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs. (Homepage of René van Bevern)

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, September 2011. Volume 7112 in Lecture Notes in Computer Science, pages 194–206, Springer.

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.

Download

The paper is availabe in PDF format. Slides of a talk are available.

BibTex Entry

For information on using BibTex in your LaTeX documents, refer to the chapter "Bibliography management" in the wikibook for LaTeX.


@inproceedings{vBHKNW11,
  Title = {Linear-Time Computation of a Linear Problem Kernel
    for Dominating Set on Planar Graphs},
  Author = {Ren\'e van Bevern and Sepp Hartung and Frank Kammer
    and Rolf Niedermeier and Mathias Weller},
  Booktitle = {Proceedings of the 6th International Symposium
    on Parameterized and Exact Computation (IPECʼ11)},
  Pages = {194--206},
  Year = {2012},
  Volume = {7112},
  Publisher = {Springer},
  Series = {LNCS},
}