Minimum connected dominating sets and maximal independent sets in unit disk graphs

In ad hoc wireless networks, a 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 the construction of a maximal independent set. The relation between the size of a maximum independent set and the size of a 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 for all unit disk graphs G. In this paper, we improve it by showing .