[ 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**

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*(*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.

*
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 (**200801_12.pdf**)

Received December 12, 2005; revised March 20, 2006; accepted March 27, 2006.

Communicated by Takeshi Tokuyama.