A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network

Deqian Fu, Lihua Han, Zifen Yang and Seong Tae Jhang

International Journal of Distributed Sensor Networks, 2016, vol. 12, issue 7, 1703201

Abstract: In the past 20 years, the connected dominating set (CDS) as a virtual backbone network has been widely used in the wireless networks. Many researchers have been devoted to designing approximate algorithms for CDS problem since constructing the minimum CDS (MCDS) is NP-hard problem. Different from the most existing algorithms with two phases, we employ greedy strategy to design a centralized algorithm GR_CDS in only one phase to get MCDS, with the time complexity of O ( ( Δ 2 + log ⠡ n ) n ) . Afterwards, another algorithm P_CDS is designed for pruning redundant nodes in the obtained MCDS with the time complexity of O ( n 2 ) .

Date: 2016
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1177/155014771703201 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:12:y:2016:i:7:p:1703201

DOI: 10.1177/155014771703201

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().