1. On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs.
- Author
-
Fujita, Satoshi
- Subjects
- *
GRAPHIC methods , *GREEDY algorithms , *ALGORITHMS , *MATHEMATICAL optimization , *WIRELESS communications - Abstract
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 and integer , there is a unit disk graph with bounded degree consisting of at least vertices for which the output of the greedy algorithm is no better than times of an optimum solution to the same graph. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF