A linear-time self-stabilizing algorithm for the minimal 2-dominating set problem in general networks
Kamei and Kakugawa have recently proposed a self-stabilizing algorithm for the minimal k-dominating set problem. Their algorithm is a general form of the maximal-independent-set algorithm proposed by Shukla et al. The results in their paper are for any tree network that assumes Dijkstra's central demon model. In particular, the worst-case stabilization time is claimed to be O(n(2)), where n is the number of nodes in the system. In this paper, we generalize their results for the case k = 2. We show that their algorithm with k = 2, when operating in any general network, is self-stabilizing under the central demon model, and solves the minimal 2-dominating set problem. We also derive that the worst-case stabilization time is linear, i.e., O(n). A bounded function technique is employed in obtaining these results.
self-stabilizing algorithm general network minimal k-dominating set tree network central demon model bounded function maximal independent set cut point