Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
复制标题
DOI：
10.1007/s00453-001-0116-5
复制
发表时间：
2002-08
期刊：
影响因子：
1.1
通讯作者：
J. Alber;H. Bodlaender;H. Fernau;T. Kloks;R. Niedermeier
中科院分区：
文献类型：
--
作者：
J. Alber;H. Bodlaender;H. Fernau;T. Kloks;R. Niedermeier
本文给出了一个算法，该算法构造性地产生了平面图的k-控制集问题的解，其中c=4^6\sqrt 34。为了得到这一结果，我们证明了控制数为γ(G)的平面图的树宽是ISO(0pt 4pt\sMashγ(G))，并且这种树分解可以在o(0pt 4pt\sMashγ(G)n)时间内找到。同样的技巧也可以用来证明k-面覆盖问题(找到一个覆盖给定平面图的所有顶点的面的大小集)可以在o(c1^\sqrt k n)时间内求解，其中1=3^36\sqrt 34，k是面覆盖集的大小。对于k-控制集的一些变体，例如k-独立控制集和k-加权控制集，在平面情形下也可以得到类似的结果。
Abstract.We present an algorithm that constructively produces a solution to thek-DOMINATING SET problem for planar graphs in timeO(c^ \sqrt k n), wherec=4^ 6\sqrt 34. To obtain this result, we show that the treewidth of a planar graph with domination numberγ (G)isO(\sqrt \rule 0pt 4pt \smash γ (G) ), and that such a tree decomposition can be found inO(\sqrt \rule 0pt 4pt \smash γ (G) n)time. The same technique can be used to show that thek-FACE COVER problem (find a sizekset of faces that cover all vertices of a given plane graph) can be solved inO(c1^ \sqrt k n)time, wherec1=3^ 36\sqrt 34andkis the size of the face cover set. Similar results can be obtained in the planar case for some variants ofk-DOMINATING SET, e.g.,k-INDEPENDENT DOMINATING SET andk-WEIGHTED DOMINATING SET.