loading...
A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph
Dalian, China December 05-December 08
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PDCAT.2005.10Sixth International Conference on Par ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.