A self-stabilizing algorithm for the distributed minimal k-redundant dominating set problem in tree networks
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate self-stabilizing distributed solutions to the minimal k-redundant dominating set (MRDS) problem in tree networks. The MRDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G=(V,E), a set M(C) V is a k-redundant dominating set of G if and only if each vertex not in M is adjacent to at least k vertices in M. We propose a self-stabilizing distributed algorithm that solves the MRDS problem for anonymous tree networks.
self-stabilizing distributed algorithm fault-tolerance minimal dominating set minimal redundant dominating set tree networks
Sayaka Kamei Hirotsugu Kakugawa
Dept.of Information Engineering, Faculty of Engineering Hiroshima University, Hiroshima, 739-8527, Japan
国际会议
成都
英文
720-724
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）