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