Title :
On Guha and Khuller´s Greedy Algorithm for Finding a Minimum CDS for Unit Disk Graphs
Author_Institution :
Dept. of Inf. Eng., Hiroshima Univ., Higashi-Hiroshima, Japan
Abstract :
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 n0 vertices for which the output of the greedy algorithm is no better than 3 - ϵ times of an optimum solution to the same graph.
Keywords :
approximation theory; computational complexity; graph theory; greedy algorithms; radio networks; relay networks (telecommunication); wireless mesh networks; Guha-Khuller greedy algorithm; NP-hard optimization problem; approximation algorithm; connected dominating set; minimum CDS; multihop wireless network; unit disk graph; Approximation algorithms; Approximation methods; Educational institutions; Greedy algorithms; Optimization; Spread spectrum communication; Wireless networks; Connected dominating set; greedy algorithm; performance ratio; unit disk graph;
Conference_Titel :
Computing and Networking (CANDAR), 2014 Second International Symposium on
DOI :
10.1109/CANDAR.2014.12