完全支配集的规约算法

骆伟忠蔡昭权兰远东刘运龙 · 2017

阅读量：101

完全支配集

NP-难解

规约

黑白着色

期刊名称：

计算机科学 2017 年 S2 期

摘要：

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