Constructing weakly connected dominating set for secure clustering in distributed sensor network

Hongjie Du, Weili Wu, Shan Shan, Donghyun Kim, Wonjun Lee

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


Secure clustering problem plays an important role in distributed sensor networks. Weakly Connected Dominating Set (WCDS) is used for solving this problem. Therefore, computing a minimum WCDS becomes an important topic of this research. In this paper, we compare the size of Maximal Independent Set (MIS) and minimum WCDS in unit disk graph. Our analysis shows that five is the least upper bound for this ratio. We also present a distributed algorithm to produce a weakly connected MIS within a factor 5 from the minimum WCDS.

Original languageEnglish
Pages (from-to)301-307
Number of pages7
JournalJournal of Combinatorial Optimization
Issue number2
Publication statusPublished - 2012 Feb

Bibliographical note

Funding Information:
Acknowledgements This research was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008). The corresponding author is Wonjun Lee.


  • DSN
  • Maximal independent set
  • Security
  • Unit disk graph
  • Weakly connected dominating set

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Constructing weakly connected dominating set for secure clustering in distributed sensor network'. Together they form a unique fingerprint.

Cite this