On Guha and Khuller's Greedy Algorithm for Finding a Minimum CDS for Unit Disk Graphs
Satoshi Fujita · 2014
A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected sub graph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm proposed by Guha and Khuller which was originally proposed for general graphs. More specifically, we show that for any fixed ϵ > 0 and integer n0≥ 1, there is a unit disk graph with bounded degree consisting of at least n0vertices for which the output of the greedy algorithm is no better than 3 - ϵ times of an optimum solution to the same graph.