Title :
An improved distributed approximation algorithm for minimum connected dominating set
Author :
Gao, Shenyong ; Zhang, Ying
Author_Institution :
Dept. of Comput. & Inf. Eng., Zhejiang Water Conservancy & Hydropower Coll., Hangzhou, China
Abstract :
To determine the minimum connected dominating set (MCDS) in wireless networks, an improved distributed approximation algorithm, which exploited the connectivity information within the 2-hops neighbors to select connected points and taken into consideration the covering relations, is presented. Simulation results showed that the proposed algorithm has fairly less connected dominating set (CDS) in terms of the time complexity and information complexity.
Keywords :
approximation theory; radio networks; 2-hop neighbor; CDS; MCDS; connected dominating set; connected point selection; improved distributed approximation algorithm; information complexity; time complexity; wireless network; Ad hoc networks; Approximation algorithms; Complexity theory; Connectors; Optimized production technology; Routing; Wireless networks;
Conference_Titel :
Natural Computation (ICNC), 2012 Eighth International Conference on
Conference_Location :
Chongqing
Print_ISBN :
978-1-4577-2130-4
DOI :
10.1109/ICNC.2012.6234531
