On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs
Satoshi Fujita · International Journal of Foundations of Computer Science · 2016
A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph 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 of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. 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 n0 vertices for which the output of the greedy algorithm is no better than 3−ε times of an optimum solution to the same graph.