| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] |
¡@
Ji-Cherng Lin, Tetz C. Huang, Cheng-Pin Wang and Chih-Yuan Chen+
Department of Computer Science and Engineering
Yuan Ze University
Chungli, 320 Taiwan
E-mail: csjclin@saturn.yzu.edu.tw
+Department of Computer Science and Information Engineering
Nanya Institute of Technology
Chungli, 320 Taiwan
The study of various dominating set problems is an important area within graph
theory. In applications, a dominating set in a system can be considered as an ideal place
for allocating resources. And, a minimal dominating set allows allocating a smaller number
of resources. Distance-versions of the concept of minimal dominating sets are more
applicable to modeling real-world problems, such as placing a smaller number of objects
within acceptable distances of a given population. However, due to the main restriction
that any processor in a distributed system can only access the data of its direct neighbors,
a self-stabilizing algorithm for finding a minimal distance-k (with k >= 2) dominating set
is hard to get, and its correctness is hard to verify. In this paper, a self-stabilizing algorithm
for finding a minimal distance-2 dominating set is proposed. The algorithm can be
applied to any distributed system that operates under the central demon model. The correctness
of the algorithm is verified.
Received February 26, 2007; revised September 4, 2007; accepted October 18, 2007.
Communicated by Chin-Laung Lei.