A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network
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 th...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2016-07-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1177/155014771703201 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849764000399622144 |
|---|---|
| author | Deqian Fu Lihua Han Zifen Yang Seong Tae Jhang |
| author_facet | Deqian Fu Lihua Han Zifen Yang Seong Tae Jhang |
| author_sort | Deqian Fu |
| collection | DOAJ |
| description | 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 ) . |
| format | Article |
| id | doaj-art-c7841b7b68b14b479ffbd0360e3e615d |
| institution | DOAJ |
| issn | 1550-1477 |
| language | English |
| publishDate | 2016-07-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-c7841b7b68b14b479ffbd0360e3e615d2025-08-20T03:05:15ZengWileyInternational Journal of Distributed Sensor Networks1550-14772016-07-011210.1177/155014771703201A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless NetworkDeqian Fu0Lihua Han1Zifen Yang2Seong Tae Jhang3 Provincial Key Laboratory for Network Based Intelligent Computing, University of Jinan, Jinnan 250022, China School of Informatics, Linyi University, Linyi 276005, China School of Informatics, Linyi University, Linyi 276005, China Department of Computer, The University of Suwon, Hwaseong-si, Gyeonggi-do 445-743, Republic of KoreaIn 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 ) .https://doi.org/10.1177/155014771703201 |
| spellingShingle | Deqian Fu Lihua Han Zifen Yang Seong Tae Jhang A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network International Journal of Distributed Sensor Networks |
| title | A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network |
| title_full | A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network |
| title_fullStr | A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network |
| title_full_unstemmed | A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network |
| title_short | A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network |
| title_sort | greedy algorithm on constructing the minimum connected dominating set in wireless network |
| url | https://doi.org/10.1177/155014771703201 |
| work_keys_str_mv | AT deqianfu agreedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT lihuahan agreedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT zifenyang agreedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT seongtaejhang agreedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT deqianfu greedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT lihuahan greedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT zifenyang greedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork AT seongtaejhang greedyalgorithmonconstructingtheminimumconnecteddominatingsetinwirelessnetwork |