An O(n 2 ) Self-Stabilizing Algorithm for Minimal Total Dominating Set in Arbitrary Graphs

Given a connected graph G=(V, E) (without any isolates), a set ${\mathcal {S}} \subseteq$V is a total dominating set if each node i$\in$V is adjacent to at least one node in $\mathcal{S}$. A total dominating set $\mathcal{S}$ is minimal iff there does not exist a node i$\in \mathcal{S}$ such that the set $\mathcal{S}$-{i} is a total dominating set. In this paper, we propose a new self-stabilizing algorithm for minimal total dominating set. The stabilization time is O(n2) steps using a central daemon, and the space requirement at each node is O(logn) bits for an arbitrary connected graph with n nodes. In the literature, the best reported stabilization time for a minimal total dominating set algorithm is O(n3) with the same space requirement at each node using central daemon.