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

Belhoul, Yacine; Yahiaoui, Saïd; Kheddouci, Hamamache

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

Date

2014-07

Authors

Belhoul, Yacine

Yahiaoui, Saïd

Kheddouci, Hamamache

Publisher

Elsevier

Abstract

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(log n) storage per node.

Keywords

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

URI

http://dl.cerist.dz/handle/CERIST/655

Collections

International Journal Papers

Full item page