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

摘要

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