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.
Bibliographical noteFunding 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.
- Maximal independent set
- 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