2012 | OriginalPaper | Chapter
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
Authors : René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, Mathias Weller
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.