Paper Info
Title
On The Power Of Lookahead In Greedy Scheme For Finding A Minimum Cds For Unit Disk Graphse
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 epsilon > 0 and integer no epsilon > 1, there is a unit disk graph with bounded degree consisting of at least no vertices for which the output of the greedy algorithm is no better than 3 - epsilon times of an optimum solution to the same graph.
Year
DOI
Venue
2016
10.1142/S0129054116500325
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
Connected dominating set, unit disk graph, greedy algorithm, performance ratio
Discrete mathematics,Dominating set,Combinatorics,Distance-hereditary graph,Independent set,Greedy coloring,Metric dimension,Mathematics,Maximal independent set,Graph coloring,Unit disk graph
Journal
Volume
Issue
ISSN
27
7
0129-0541
Citations 
PageRank 
References 
0
0.34
0
Authors
1
Name
Order
Citations
PageRank
Satoshi Fujita14618.99