完全p-支配集的参数算法

• 作者: 冯启龙 王建新 陈建二 骆伟忠
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 完全p-支配集 DG模型 固定参数可解 树分解 动态规划
• 年，卷（期）: 2013,（9）
• 所属期刊栏目: 计算机理论
• 页码范围: 1868-1879
• 页数: 12页
• 分类号: TP301
• 字数: 14765字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2013.01868

摘要

完全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为问题解的大小.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	骆伟忠	中南大学信息科学与工程学院	2	31	2.0	2.0
5	冯启龙	中南大学信息科学与工程学院	11	38	4.0	6.0