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

作者：Belhoul Yacine^*; Yahiaoui Said; Kheddouci Hamamache

来源：Information Processing Letters, 2014, 114(7): 339-343.

DOI：10.1016/j.ipl.2014.02.002

• Distributed self-stabilizing algorithms
• Graph algorithms
• Minimal total dominating set
• Minimal total k-domination
• k-Tuple total dominating set

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) moves starting from any arbitrary state, and require O(logn) storage per node.

• 出版日期2014-7