JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]


Journal of Information Science and Engineering, Vol. 24 No. 1, pp. 175-187


A Linear-Time Self-Stabilizing Algorithm for the Minimal 2-Dominating Set Problem in General Networks


Tetz C. Huang, Chih-Yuan Chen and Cheng-Pin Wang
Department of Computer Engineering and Science 
Yuan Ze University 
Chungli, 320 Taiwan 
E-mail: cstetz@saturn.yzu.edu.tw


    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 maximalindependent- 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 worstcase stabilization time is claimed to be O(n2), 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.


Keywords: self-stabilizing algorithm, central demon model, maximal independent set, minimal k-dominating set, tree network, general network, bounded function, cut point

  Retrieve PDF document (JISE_200801_12.pdf)