On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2016-11, Vol.27 (7), p.829-843
Main Author: Fujita, Satoshi
Format: Article
Language:English
Subjects:
Decision trees
Graph theory
Graphs
Greedy algorithms
Lower bounds
Virtual networks
Wireless networks
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 n 0 ≥ 1 , there is a unit disk graph with bounded degree consisting of at least n 0 vertices for which the output of the greedy algorithm is no better than 3 − ε times of an optimum solution to the same graph.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054116500325