《计算机学报》文章摘要   全文下载
文章题目	完全p-支配集的参数算法
作者	骆伟忠1),2) 冯启龙1) 王建新1) 陈建二1)
作者单位	1)(中南大学信息科学与工程学院 长沙 410083) 2)(惠州学院计算机科学系 广东 惠州 516007)
发表年份	2013
发表月份	9期(1868—1879)
文章摘要	摘要 完全p-支配集是一个著名的NP-难问题，在无线传感网络中被用于构建无线传感节点的自我保护网络.该文主要研究完全p-支配集在DG(Disk Graph)模型及其特殊模型上的参数复杂性及参数算法设计.首先证明完全p-支配集在顶点度受限的UDG(Unit Disk Graph)上仍是NP-难的.为了深入理解完全p-支配集在UDG模型上的难解性根源，利用参数化规约进一步研究了完全p-支配集在UDG上的参数复杂性.基于难解性根源的分析，最后利用树分解技术和动态规划技术，针对平面图(一种特殊DG模型)上的完全p-支配集，设计了一个时间为O((2p+2)19.1?kk3n+n3)的精确算法，其中n为给定实例中的顶点个数，k为问题解的大小. 关键词 完全p-支配集；DG模型；固定参数可解；树分解；动态规划 中图法分类号 TP301 DOI号 10.3724/SP.J.1016.2013.01868