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 ^{+}**

Yuan Ze University

Chungli, 320 Taiwan

E-mail: csjclin@saturn.yzu.edu.tw

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.

*
Keywords:
*
minimal distance-2 dominating set, self-stabilizing algorithm, Dijkstra¡¦s central
demon model, distributed system, legitimate configuration

Retrieve PDF document (**200811_06.pdf**)

Received February 26, 2007; revised September 4, 2007; accepted October 18, 2007.

Communicated by Chin-Laung Lei.