完全支配集的规约算法

摘要：

完全支配集是一个著名的NP难解问题,在无线传感器网络中具有重要应用.主要研究了能降低问题规模的规约化算法设计.通过对问题结构进行深入分析并对图中顶点进行着色,得到图中顶点之间的新的组合特性,在此基础上提出一系列高效的多项式时间的局部规约规则.证明了规约规则的正确性,并通过仿真实验验证了规约规则的有效性.

关键词：完全支配集、NP-难解、规约、黑白着色

所属期刊栏目：44

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金项目61370185;广东省自然科学基金博士启动项目2015A030310445;惠州学院博士启动项目C513.0211

在线出版日期：2018-01-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：115-118,132