loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT'05)
A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph
Dalian, China
December 05-December 08
ISBN: 0-7695-2405-2
Ankur Jain, Indian Institute of Technology, Kharagpur, India
Arobinda Gupta, Indian Institute of Technology, Kharagpur, India
A connected dominating set of a graph G is a set of nodes of G such that every node in G is either in the set or is adjacent to some node in the set, and the graph induced by the elements of the set is connected. Connected dominating sets have major applications in routing in wireless ad-hoc networks. In this paper, we present a distributed self-stabilizing algorithm for finding a connected dominating set of a graph. Starting from an arbitrary initial state, the algorithm finds a connected dominating set in O(N^2) time, where N is the number of nodes. We also show detailed simulation results to indicate that in practice, the algorithm finds small-sized connected dominating sets in a short time.
Citation:
Ankur Jain, Arobinda Gupta, "A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph," pdcat, pp.615-619, Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.