论文研究一种高效的最小连通支配集贪心算法.pdf

连通支配集（CDS）在无线网络设计中有着广泛应用，现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS），依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点，当删除处理节点后剩余点不连通时减少处理的节点数，进而把节点分为支配点和受支配点；最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明，GCDS算法具有较低的时间复杂度，所得到的连通支配集大小优于已有算法。