Efficient Distributed Approximation Algorithm for    Minimum Connected Dominating Set

doi:10.3969/j.issn.1000-3428.2008.23.050

Computer Engineering ›› 2008, Vol. 34 ›› Issue (23): 139-141,. doi: 10.3969/j.issn.1000-3428.2008.23.050

• Networks and Communications • Previous Articles Next Articles

Efficient Distributed Approximation Algorithm for Minimum Connected Dominating Set

ZHANG Min, ZHANG Ying, CHEN Qin

(Institute of Intelligent and Software Technology, Hangzhou Dianzi University, Hangzhou 310018)

Received:1900-01-01 Revised:1900-01-01 Online:2008-12-05 Published:2008-12-05

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

张旻，张颖，陈勤

(杭州电子科技大学智能与软件技术研究所，杭州 310018)

Abstract

Abstract: 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 and message complexity is , which are all better than TFA algorithm and Alzoubi and Wan’s algorithm.

Key words: Ad Hoc networks, distributed, maximal independent set, minimum connected dominating set

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

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

CLC Number:

TP393.07

ZHANG Min; ZHANG Ying; CHEN Qin. Efficient Distributed Approximation Algorithm for Minimum Connected Dominating Set[J]. Computer Engineering, 2008, 34(23): 139-141,.

张旻;张颖;陈勤. 高效的分布式最小连通支配集近似算法[J]. 计算机工程, 2008, 34(23): 139-141,.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2008.23.050

http://www.ecice06.com/EN/Y2008/V34/I23/139

[1]	BI Xiang, HUANG Huang, ZHANG Benhong, WEI Xing. V2V Composite Routing Algorithm for Internet of Vehicles Based on Clustering and Improved Q-Learning [J]. Computer Engineering, 2023, 49(3): 221-230,247.
[2]	SU Ruiguo, YANG Jian, QIN Jiwei, WU Xiaoxiong, JIA Zhenhong. Research on Lightweight Consensus Algorithm Based on IoT Blockchain [J]. Computer Engineering, 2023, 49(2): 175-180.
[3]	DING Qingfeng, LI Jinguo. A Distributed Abnormal Traffic Detection Scheme in Internet of Things Environment [J]. Computer Engineering, 2022, 48(8): 152-159.
[4]	HUANG Huawei, KONG Wei, PENG Xiaowen, ZHENG Zibin. Survey on Blockchain Sharding Technology [J]. Computer Engineering, 2022, 48(6): 1-10.
[5]	WANG Jinsong, YANG Weizheng, ZHAO Zening, WEI Jiajia. Survey of Directed Acyclic Graph Based Blockchain Technology [J]. Computer Engineering, 2022, 48(6): 11-23.
[6]	CHEN Huang, CHEN Rui, KUANG Zhufang, HUANG Huajun. A Frequency-domain Correlation Distributed Diffusion Least Mean Square Algorithm [J]. Computer Engineering, 2022, 48(5): 215-221.
[7]	YANG Ke, ZHANG Fan, GUO Wei, ZHAO Bo, MU Qing. A Method for Solving the Metadata Randomness Problem of Mimic Storage [J]. Computer Engineering, 2022, 48(2): 140-146,155.
[8]	BAI Caitong, CUI Xiaolong, LI Ai. Robust Speech Recognition Technology Based on Federal Learning with Local Distillation [J]. Computer Engineering, 2022, 48(10): 103-109.
[9]	WEI Xiuran, WANG Feng. Data Replication Strategy of Cloud Storage Based on Coordinator and Genetic Algorithm [J]. Computer Engineering, 2021, 47(8): 124-130,139.
[10]	YI Peihuai, LI Weidong, LIN Tao, ZOU Jiaheng, DENG Ziyan, LIU Yan. Application of GPU in Fast Muon Simulation [J]. Computer Engineering, 2021, 47(8): 100-108.
[11]	MA Jiajia, ZHANG Zhiqiang, CAO Suzhen, DOU Fengge, DING Xiaohui, WANG Caifen. Distributed Attribute-Based Encryption Scheme Based on Fog Nodes [J]. Computer Engineering, 2021, 47(6): 38-43.
[12]	ZHANG Benhong, WU Haohao, YU Lei. Contention-based Time Division Multiple Access MAC Protocol in Vehicular Ad Hoc Networks [J]. Computer Engineering, 2021, 47(5): 154-159.
[13]	LI Bowen, XIE Zaipeng, MAO Yingchi, XU Yuanyuan, ZHU Xiaorui, ZHANG Ji. A Synchronized Gradient Descent Algorithm Based on Distributed Coding [J]. Computer Engineering, 2021, 47(4): 68-76,83.
[14]	ZHANG Ji, XIE Zaipeng, MAO Yingchi, XU Yuanyuan, ZHU Xiaorui, LI Bowen. Fault-Tolerant Algorithm Combined with Distributed Coding Computing in MapReduce Framework [J]. Computer Engineering, 2021, 47(4): 173-179.
[15]	GAO Zixuan, ZHENG Quan. Research on Content Priority-Based Caching Strategy in NDMANET [J]. Computer Engineering, 2021, 47(3): 190-195.

Please choose a citation manager

Content to export

Efficient Distributed Approximation Algorithm for Minimum Connected Dominating Set

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

模态框（Modal）标题

Please choose a citation manager

Content to export

Efficient Distributed Approximation Algorithm for Minimum Connected Dominating Set

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments