Tighter approximation bounds for minimum CDS in wireless ad hoc networks

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

28 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationAlgorithms and Computation
Subtitle of host publication20th International Symposium, ISAAC 2009, Proceedings
PublisherSpringer Verlag
Pages699-709
Volume5878 LNCS
ISBN (Print)3642106307, 9783642106309
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title20th Annual International Symposium on Algorithms and Computation (ISAAC 2009)
PlaceUnited States
CityHonolulu
Period16 - 18 December 2009

Abstract

Connected dominating set (CDS) has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in wireless ad hoc networks 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 . 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. © 2009 Springer-Verlag Berlin Heidelberg.

Citation Format(s)

Tighter approximation bounds for minimum CDS in wireless ad hoc networks. / Li, Minming; Wan, Peng-Jun; Yao, Frances.

Algorithms and Computation: 20th International Symposium, ISAAC 2009, Proceedings. Vol. 5878 LNCS Springer Verlag, 2009. p. 699-709 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)