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

被引：7

作者：

Belhoul, Yacine ^{[1
,2
]}

Yahiaoui, Said ^{[1
,2
]}

Kheddouci, Hamamache ^{[3
]}

机构：

[1] Univ A Mira, Dept Informat, Bejaia 06000, Algeria

[2] CERIST, Algiers 16030, Algeria

[3] Univ Lyon 1, CNRS, LIRIS, UMR5205, F-69622 Villeurbanne, France

来源：

INFORMATION PROCESSING LETTERS | 2014年 / 114卷 / 07期

关键词：

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

D O I：

10.1016/j.ipl.2014.02.002

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：339 / 343

页数：5