Self-Stabilizing Algorithm for Minimal Dominating Set with Safe Convergence in an Arbitrary Graph
Yihua Ding, James Z. Wang, Pradip K. Srimani · Parallel Processing Letters · 2015
In a graph or a network [Formula: see text], a set [Formula: see text] is a dominating set if each node in [Formula: see text] is adjacent to at least one node in [Formula: see text]. A dominating set [Formula: see text] is called minimal when there does not exist a node [Formula: see text] such that the set [Formula: see text] is a dominating set. In this paper, we propose a new self-stabilizing algorithm for minimal dominating set. It has safe convergence property under synchronous daemon in the sense that starting from an arbitrary state, it quickly converges to a dominating set (a safe state) in two rounds, and then stabilizes in a minimal dominating set (the legitimate state) in [Formula: see text] rounds without breaking safety during the convergence interval, where n is the number of nodes. Space requirement at each node is [Formula: see text] bits.