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
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb