Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

Dubhashi, Devdatt ; Mei, Alessandro ; Panconesi, Alessandro ; Radhakrishnan, Jaikumar ; Srinivasan, Aravind (2005) Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons Journal of Computer and System Sciences, 71 (4). pp. 467-479. ISSN 0022-0000

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/j.jcss.2005.04.002

Abstract

Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O(log Δ) times the optimum, Δ being the maximum degree of the input network. This is best-possible if NP⊈DTIME[nO(log log n)] and if the processors are required to run in polynomial-time. We then show how to construct dominating sets that have the above properties, as well as the "low stretch" property that any two adjacent nodes in the network have their dominators at a distance of at most in the output network. (Given a dominating set S, a dominator of a vertex u is any v∈S such that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Ad hoc Networks; Dominating Sets; Distributed Algorithms
ID Code:89508
Deposited On:27 Apr 2012 13:40
Last Modified:27 Apr 2012 13:40

Repository Staff Only: item control page