关于连通误报容错支配集的一个启发式算法

A heuristic algorithm about connected liar's domination problems

研究了一般网络拓扑图中的连通误报容错支配集的构造算法.首先给出了误报容错支配集的一个精确算法,但是算法的复杂度达到了指数级别.随后又提出了误报容错支配集的一个多项式时间的启发式算法,最后证明了算法的正确性并通过仿真实验验证了算法的有效性.

This paper mainly studies a heuristic algorithm about connected liar＇s domination problems in general network graphs. We first gave an exact algorithm with the complexity of index level for constructing a minimum connected liar＇s domination problem in general networks. Therewith, we proposed a polynomial heuristic algorithm. Finally, we proved the correction of the algorithm and verified the effectiveness of the algorithm by simulation experiments.