loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
23rd IEEE International Conference on Distributed Computing Systems (ICDCS'03)
Weakly-Connected Dominating Sets and Sparse Spanners in Wireless Ad Hoc Networks
Providence, Rhode Island
May 19-May 22
ISBN: 0-7695-1920-2
Khaled M. Alzoubi, Illinois Institute of Technology
Peng-Jun Wan, Illinois Institute of Technology
Ophir Frieder, Illinois Institute of Technology
A set S is dominating if each node in the graph G = (V,E) is either in S or adjacent to at least one of the nodes in S. The subgraph weakly induced by S is the graph G' = (V,E') such that each edge in E' has at least one end point in S. The set S is a weakly-connected dominating set (WCDS) of G if S is dominating and G' is connected. G' is a sparse spanner if it has linear edges. In this paper, we present two distributed algorithms for finding a WCDS in O(n) time. The first algorithm has an approximation ratio of 5, and requires O(n log n) messages. The second algorithm has a larger approximation ratio, but it requires only O(n) messages. The graph G' generated by the second algorithm forms a sparse spanner with a topological dilation of 3, and a geometric dilation of 6.
Index Terms:
weakly-connected dominating set, maximal independent set, sparse spanner
Citation:
Khaled M. Alzoubi, Peng-Jun Wan, Ophir Frieder, "Weakly-Connected Dominating Sets and Sparse Spanners in Wireless Ad Hoc Networks," icdcs, pp.96, 23rd IEEE International Conference on Distributed Computing Systems (ICDCS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.