A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph

Abstract

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.