TY - GEN

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

AU - Van Bevern, René

AU - Hartung, Sepp

AU - Kammer, Frank

AU - Niedermeier, Rolf

AU - Weller, Mathias

PY - 2012/3/22

Y1 - 2012/3/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84858397665&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28050-4_16

DO - 10.1007/978-3-642-28050-4_16

M3 - Conference contribution

AN - SCOPUS:84858397665

SN - 9783642280498

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 194

EP - 206

BT - Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers

T2 - 6th International Symposium on Parameterized and Exact Computation, IPEC 2011

Y2 - 6 September 2011 through 8 September 2011

ER -