Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs

Wei Wuli, Hongwei Du, Xiaohua Jia, Yingshu Li, Scott C.-h. Huang, Ding‐Zhu DuUniversity 2004

Abstract

In ad hoc wireless networks, the connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on construction of maximal independent set. The relation between the size\nmis(G) of a maximum independent set and the size cds(G) of minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)<=4*cds(G)+1 for all unit disk graph G. In this paper, we improve it by showing mis(G)<=3.8*cds(G)+1.2.
BibTeX
@inproceedings{wuli2004maximal,
  author = {Wei Wuli and Hongwei Du and Xiaohua Jia and Yingshu Li and Scott C.-H. Huang and Ding‐Zhu Du},
  title = {{Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs}},
  booktitle = {University},
  year = {2004},
}

Loading related content...

Figure