Algorithms for minimum m-connected k-tuple dominating set problem

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

31 Scopus Citations
View graph of relations

Author(s)

  • Weiping Shang
  • Pengjun Wan
  • Frances Yao
  • Xiaodong Hu

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)241-247
Journal / PublicationTheoretical Computer Science
Volume381
Issue number1-3
Publication statusPublished - 22 Aug 2007

Abstract

In wireless sensor networks, a virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-tuple dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. We propose three centralized algorithms with small approximation ratios for small m and improve the current best results for small k. © 2007 Elsevier Ltd. All rights reserved.

Research Area(s)

  • Approximation algorithm, Connected dominating set, k-vertex connectivity, Wireless sensor networks

Citation Format(s)

Algorithms for minimum m-connected k-tuple dominating set problem. / Shang, Weiping; Wan, Pengjun; Yao, Frances et al.
In: Theoretical Computer Science, Vol. 381, No. 1-3, 22.08.2007, p. 241-247.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review