| [ Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] |
¡@
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.
Received December 12, 2005; revised March 20, 2006; accepted March 27, 2006.
Communicated by Takeshi Tokuyama.