A distributed approximation algorithm for the bottleneck connected dominating set problem Academic Article

abstract

• Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication between the sensors. Connected dominating sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and to minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included. 2011 Springer-Verlag.

authors

• Butenko, Sergiy

published proceedings

• OPTIMIZATION LETTERS

author list (cited authors)

• Verma, A., & Butenko, S.

citation count

• 1

complete list of authors

• Verma, Anurag||Butenko, Sergiy

publication date

• December 2012

publisher

• Springer Nature  Publisher

published in

• Optimization Letters  Journal

keywords

• Bottleneck Connected Dominating Set
• Distributed Algorithm
• Wireless Networks

Digital Object Identifier (DOI)

• 10.1007/s11590-011-0314-2

start page

• 1583

end page

• 1595

volume

• 6

issue

• 8

URL

• http://dx.doi.org/10.1007/s11590-011-0314-2