A Self-Stabilizing Approximation Algorithm for the Distributed Minimum k-Domination(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate a self-stabilizing distributed approximation for the minimum k-dominating set (KDS) problem in general networks. The minimum KDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G= (V, E), a set D_k⊆V is a KDS of G if and only if each vertex not in D_k is adjacent to at least k vertices in D_k. The approximation ratio of our algorithm is Δ/k (1+<k-1>/<Δ+1>), where Δ is the maximum degree of G, in the networks of which the minimum degree is more than or equal to k.
社団法人電子情報通信学会の論文
2005-05-01