Tighter approximation bounds for minimum CDS in unit disk graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

20 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1000-1021
Journal / PublicationAlgorithmica (New York)
Volume61
Issue number4
Publication statusPublished - Dec 2011

Abstract

Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased algorithms, the relation between the independence number α and the connected domination number γ c of a unit-disk graph plays the key role. The best-known relation between them is α≤32/3γc+1 . In this paper, we prove that α≤3.4306γ c +4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature. © 2011 Springer Science+Business Media, LLC.

Research Area(s)

  • Approximation algorithm, Connected dominating set, Geometric analysis, Wireless ad hoc networks

Citation Format(s)

Tighter approximation bounds for minimum CDS in unit disk graphs. / Li, Minming; Wan, Peng-Jun; Yao, Frances.

In: Algorithmica (New York), Vol. 61, No. 4, 12.2011, p. 1000-1021.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal