基于分享度的最小连通支配集求解算法  

Minimum Connected Dominating Set Solution Algorithm Based on Share Degree

作　　者：赵学锋[1] 陈祥恩[2] 

机构地区：[1]西北师范大学计算机科学与工程学院,兰州730070 [2]西北师范大学数学与统计学院,兰州730070

出　　处：《计算机工程》2013年第6期134-137,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(61163037)

摘　　要：以节点分享度作为选择分配点的优先级,提出一种最小连通支配集(CDS)求解算法。从根节点开始,将具有局部最大分享度的节点作为支配点,选择连接点与已确定的支配点连通,逐步构造网络的支配树,分析支配树的直径,计算支配树的平均跳数距离(AHD),从而评价网络的通信成本。实验结果表明,与CDS-BD-C2算法相比,该算法得到的CDS规模较小,且支配树的AHD平均减少12%。Making point Share Degree（SD） as the priority of selection control point, a new solution algorithm for computing the minimum Connected Dominating Set（CDS） in networks is proposed. Starting from root node, it iteratively selects nodes with maximum share degree in its neighborhood as dominators and some intermediate nodes as connector link to determined dominators previously, and a dominating tree is found gradually. The diameter of the dominating tree is analyzed, moreover its Average Hop Distances（AHD） is calculated in order to evaluate communication costs in networks. Experimental results show that this algorithm can construct smaller CDS than related works, and the AHD is reduced by 12% on average, compared with the CDS-BD-C2 algorithm.

关 键 词：最小连通支配集 支配 连接点 分享度 平均跳数距离 单位圆盘图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]