An O(n2) Self-Stabilizing Algorithm for Minimal Total Dominating Set in Arbitrary Graphs
Yihua Ding, James Z. Wang, Pradip K. Srimani · 2020
Given a connected graph G = (V, E) (without any isolates), a set S ⊆ V is a total dominating set if each node i ∈ V is adjacent to at least one node in S. A total dominating set S is minimal iff there does not exist a node i ∈ S such that the set 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(log n) 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.