A Self-Stabilizing Algorithm for Two Disjoint Minimal Dominating Sets with Safe Convergence

摘要

If a graph G = (V, E) has no isolated nodes and D ⊂ V is a minimal dominating set, then V D is a dominating set [1]. In such graphs, there are two disjoint minimal dominating sets A and B. In this paper, we propose an asynchronous self-stabilizing distributed algorithm for finding such a pair of sets with safe convergence. We assume that the first feasible safe configuration satisfies A is a dominating set. The second feasible safe configuration satisfies A is a minimal dominating set. The third feasible safe configuration satisfies A is a minimal dominating set, B is a dominating set and A and B are disjoint. Finally, the legitimate configuration satisfies A and B are disjoint minimal dominating sets.