A self-stabilizing approximation algorithm for the distributed minimum k-domination

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 subset of V is a KDS of G if and only if each vertex not in Dk is adjacent to at least k vertices in D-k. The approximation ratio of our algorithm is (Delta)/(k)(1+(k-1)/(Delta+1)), where Delta is the maximum degree of G, in the networks of which the minimum degree is more than or equal to k.