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

Efficient Distributed Approximation Algorithm for Minimum Connected Dominating Set

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

Based on Alzoubi and Wan＇s algorithm, this paper proposes Effective Distributed Minimum Connected Dominating Set Algorithm （EDMCDS） by choosing connector node with two hop local network topology information. Analysis shows that the size of connected dominating set with EDMCDS is （5.8＋ln4）opt＋1.2, time complexity is O（△｜MIS｜） and message complexity is O（4｜E｜） , which are all better than TFA algorithm and Alzoubi and Wan＇s algorithm.