高效的分布式最小连通支配集近似算法

• 作者: 张旻 张颖 陈勤
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: Ad Hoc网络 分布式 极大独立集 最小连通支配集
• 年，卷（期）: 2008,（23）
• 所属期刊栏目: 网络与通信
• 页码范围: 139-141,163
• 页数: 4页
• 分类号: TP393.07
• 字数: 4137字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2008.23.050

摘要

在Alzoubi and Wan's算法的基础上,利用2跳局部网络拓扑信息选择连通点,提出一个高效的分布式最小连通支配集算法EDMCDS.理论分析表明,EDMCDS算法生成的连通支配集大小为(5.8+ln4)opt+1.2,时间复杂度为O(△\MIS\),信息复杂度为O(4lEI).与TFA和Alzoubi and Wan's算法相比,该算法生成的连通支配集更小,时间复杂度和信息复杂度也有所降低.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈勤	杭州电子科技大学智能与软件技术研究所	82	349	11.0	13.0
2	张旻	杭州电子科技大学智能与软件技术研究所	31	263	7.0	15.0
3	张颖	杭州电子科技大学智能与软件技术研究所	7	27	2.0	5.0