DocumentCode
2556646
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
fYear
2012
fDate
29-31 May 2012
Firstpage
1019
Lastpage
1022
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Natural Computation (ICNC), 2012 Eighth International Conference on
Conference_Location
Chongqing
ISSN
2157-9555
Print_ISBN
978-1-4577-2130-4
Type
conf
DOI
10.1109/ICNC.2012.6234531
Filename
6234531
Link To Document