作　　者： ; ; ; ;

机构地区： 中南大学信息科学与工程学院

出　　处： 《计算机学报》 2013年第9期1868-1879,共12页

摘　　要： 完全p-支配集是一个著名的NP-难问题,在无线传感网络中被用于构建无线传感节点的自我保护网络.该文主要研究完全p-支配集在DG(Disk Graph)模型及其特殊模型上的参数复杂性及参数算法设计.首先证明完全p-支配集在顶点度受限的UDG(Unit Disk Graph)上仍是NP-难的.为了深入理解完全p-支配集在UDG模型上的难解性根源,利用参数化规约进一步研究了完全p-支配集在UDG上的参数复杂性.基于难解性根源的分析,最后利用树分解技术和动态规划技术,针对平面图(一种特殊DG模型)上的完全p-支配集,设计了一个时间为O((2p+2)19.1·2^(1-k)k3 n+n3)的精确算法,其中n为给定实例中的顶点个数,k为问题解的大小. Total p-Dominating Set is a famous NP-hard problem, and has important applications in wireless networks. In wireless networks, Total p-Dominating Set is usually used to construct the self-protection network for wireless nodes. In this paper, we mainly study the Total p-Domina- ting Set problem in disk graphs and some more restricted classes of disk graphs from the viewpoint of parameterized complexity and parameterized algorithms. We first prove that Total p-Dominating Set is still NP-hard in unit disk graphs with bounded vertex degree. To gain insight into the source of complexity of Total p-Dominating Set in unit disk graphs, based on parameterized reduction, we further study the parameterized complexity of the considered problem in unit disk graphs. By the method of tree decomposition and dynamic programming, we finally design an exact algorithm with running time O（ （2p＋ 2）^ 19.1√k 3 n＋ n3 ） for Total p -Dominating Set in planar graphs （a restricted class of disk graphs）, where n denotes the number of vertices in the given instance, and k is the size of problem solution.

关 键 词： 完全 支配集 模型 固定参数可解 树分解 动态规划

领　　域： [自动化与计算机技术] [自动化与计算机技术]