On greedy construction of connected dominating sets in wireless networks

Yingshu Li, My T. Thai, Feng Wang, Chih Wei Yi, Peng Jun Wan, Ding Zhu Du

Research output: Contribution to journalReview articlepeer-review

165 Scopus citations


Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP-hard. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same.

Original languageEnglish (US)
Pages (from-to)927-932
Number of pages6
JournalWireless Communications and Mobile Computing
Issue number8
StatePublished - Dec 2005
Externally publishedYes


  • Connected dominating set
  • Greedy algorithm
  • Maximal independent set
  • Wireless network

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On greedy construction of connected dominating sets in wireless networks'. Together they form a unique fingerprint.

Cite this