摘要： 针对最小连通r-跳k-支配集的求解问题，提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解，从中选出度数最小的节点，通过判断节点的连通性决定是否将该节点从当前可行解中删除，由此逐步缩小连通支配集的规模，直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验，结果表明，相比同类算法，该算法得到的连通r-跳k-支配点集更少，且性能稳定。

关键词: 最小连通r-跳k-支配集, 启发式算法, 单位圆盘图, 广度优先搜索, 节点度

Abstract: For computing the minimum connected r-hop k-dominating set, a heuristic algorithm is proposed based on greedy strategy about node degrees. It starts with an initial solution containing all nodes in the network, from which it repeatedly selects a node with minimal degree and decides whether to remove the node from current feasible solution according to connectivity. The size of feasible solution is reduced gradually, until all nodes are processed. Its time complexity is analyzed in Unit Disk Graph(UDG). The numerical experimental results show that the new algorithm generates smaller connected r-hop k-dominated set and achieves more stable performance than existing related algorithms.

Key words: minimum connected r-hop k-dominating set, heuristic algorithm, Unit Disk Graph(UDG), heap, Breadth First Search(BFS), node degree

中图分类号: 

• TP393