Self-Stabilizing Algorithm for Minimal Dominating Set with Safe Convergence in an Arbitrary Graph
Abstract
In a graph or a network , a set is a dominating set if each node in is adjacent to at least one node in . A dominating set is called minimal when there does not exist a node such that the set 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 rounds without breaking safety during the convergence interval, where n is the number of nodes. Space requirement at each node is bits.
Communicated by K. Qiu


