一种高效的最小连通支配集贪心算法

作     者：高红玉 赵学锋 王占华 GAO Hongyu;ZHAO Xuefeng;WANG Zhanhua

作者机构：西北师范大学数学与信息科学学院兰州730070 

基　　金：甘肃省科技攻关项目(No.2GS035-A052-011) 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2012年第48卷第13期

页      码：89-93页

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

主 题 词：最小连通支配集 单位圆盘图 贪心算法 广度优先搜索 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1002-8331.2012.13.020

馆 藏 号：203105742...