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

摘要：

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

关键词：Ad、Hoc网络、分布式、极大独立集、最小连通支配集

所属期刊栏目：34

分类号：TP393.07(计算技术、计算机技术)

资助基金：现代通信国家重点实验室基金资助项目9140C110206070C11;杭州电子科技大学校科学研究基金资助项目KYF071506005

在线出版日期：2009-02-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：139-141,163