[ Previous [ 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 (January 2008)

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

Full Text () Retrieve PDF document (200801_12.pdf)

Received December 12, 2005; revised March 20, 2006; accepted March 27, 2006.
Communicated by Takeshi Tokuyama.