Simpler Linear-Time Kernelization for Planar Dominating Set
Simpler Linear-Time Kernelization for Planar Dominating Set
复制标题
DOI：
10.1007/978-3-642-28050-4_15
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
T. Hagerup
中科院分区：
文献类型：
--
作者：
T. Hagerup
我们描述了一种线性时间算法，该算法输入一个平面图，输出一个平面图，大小为0 (k)，具有控制数，其中控制数g，即最小控制集的大小inG。在参数化计算语言中，新算法是np -完全平面支配集问题的线性时间核化，产生线性大小的核。这样的算法以前是已知的（van Bevern et al.，这些程序），但新的算法及其分析要简单得多。
We describe a linear-time algorithm that inputs a planar graphGand outputs a planar graph of sizeO(k) and with domination numberk, wherekis the domination number ofG, i.e., the size of a smallest dominating set inG. In the language of parameterized computation, the new algorithm is a linear-time kernelization for the NP-completePlanar Dominating Setproblem that produces a kernel of linear size. Such an algorithm was previously known (van Bevern et al., these proceedings), but the new algorithm and its analysis are considerably simpler.