Efficient self-stabilizing algorithms for minimal total k-dominating sets in graphs

• We propose an efficient self-stabilizing distributed algorithm for the minimal total dominating set problem.
• We generalize the proposed algorithm for the minimal total k-dominating set problem.
• Under an unfair distributed scheduler, the proposed algorithms converge in O(mn)O(mn) moves.

We propose the first polynomial self-stabilizing distributed algorithm for the minimal total dominating set problem in an arbitrary graph. Then, we generalize the proposed algorithm for the minimal total k  -dominating set problem. Under an unfair distributed scheduler, the proposed algorithms converge in O(mn)O(mn) moves starting from any arbitrary state, and require O(logn) storage per node.