Algorithms for minimum m-connected k-tuple dominating set problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 241-247 |
Journal / Publication | Theoretical Computer Science |
Volume | 381 |
Issue number | 1-3 |
Publication status | Published - 22 Aug 2007 |
Link(s)
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.
In: Theoretical Computer Science, Vol. 381, No. 1-3, 22.08.2007, p. 241-247.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review