分布式最小连通支配集启发式算法

• 作者: FAN Wen-tao 张旻 范文涛 陈勤
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 有效度 支配节点 极大独立集 最小连通支配集
• 年，卷（期）: 2009,（10）
• 所属期刊栏目: 网络与通信
• 页码范围: 92-94
• 页数: 3页
• 分类号: TP393.07
• 字数: 3374字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2009.10.030

摘要

针对Ad Hoc 网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈勤	杭州电子科技大学软件与智能技术研究所	82	349	11.0	13.0
2	张旻	杭州电子科技大学软件与智能技术研究所	31	263	7.0	15.0
3	FAN Wen-tao	杭州电子科技大学软件与智能技术研究所	1	9	1.0	1.0
4	范文涛	杭州电子科技大学软件与智能技术研究所	2	13	2.0	2.0