Linear-time computation of a linear problem kernel for dominating set on planar graphs

René Van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, Mathias Weller

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationParameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers
Pages194-206
Number of pages13
DOIs
Publication statusPublished - 22 Mar 2012
Externally publishedYes
Event6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrucken, Germany
Duration: 6 Sep 20118 Sep 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7112 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Symposium on Parameterized and Exact Computation, IPEC 2011
CountryGermany
CitySaarbrucken
Period06.09.201108.09.2011

Fingerprint Dive into the research topics of 'Linear-time computation of a linear problem kernel for dominating set on planar graphs'. Together they form a unique fingerprint.

Cite this