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
相关论文
共 31 条
  • [21] Self-Stabilizing k-out-of-l Exclusion on Tree Networks
    Datta, Ajoy K.
    Devismes, Stephane
    Horn, Florian
    Larmore, Lawrence L.
    2009 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-5, 2009, : 1168 - +
  • [22] SELF-STABILIZING k-out-of-l EXCLUSION IN TREE NETWORKS
    Datta, Ajoy K.
    Devismes, Stephane
    Horn, Florian
    Larmore, Lawrence L.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2011, 22 (03) : 657 - 677
  • [23] A new self-stabilizing algorithm for maximal p-star decomposition of general graphs
    Neggazi, Brahim
    Haddad, Mohammed
    Kheddouci, Hamamache
    INFORMATION PROCESSING LETTERS, 2015, 115 (11) : 892 - 898
  • [24] Cached Sensornet Transformation of Non-silent Self-stabilizing Algorithms with Unreliable Links
    Kakugawa, Hnotsugu
    Yamauchi, Yukiko
    Kamei, Sayaka
    Masuzawa, Toshimitsu
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, PROCEEDINGS, 2009, 5873 : 428 - 442
  • [25] Analysis of a memory-efficient self-stabilizing BFS spanning tree construction
    Datta, Ajoy K.
    Devismes, Stephane
    Johnen, Colette
    Larmore, Lawrence L.
    THEORETICAL COMPUTER SCIENCE, 2023, 955
  • [26] From State to Link-Register Model: A transformer for Self-Stabilizing Distributed Algorithms
    Cohen, Johanne
    Manoussakis, George
    Pilard, Laurence
    2023 25TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING, SYNASC 2023, 2023, : 114 - 121
  • [27] Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model
    Lin, Ji-Cherng
    Chiu, Ming-Yi
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (01) : 140 - 148
  • [28] On the performance of Dijkstra's third self-stabilizing algorithm for mutual exclusion and related algorithms
    Chernoy, Viacheslav
    Shalom, Mordechai
    Zaks, Shmuel
    DISTRIBUTED COMPUTING, 2010, 23 (01) : 43 - 60
  • [29] A self-stabilizing memory efficient algorithm for the minimum diameter spanning tree under an omnipotent daemon
    Blin, Lelia
    Boubekeur, Fadwa
    Dubois, Swan
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2018, 117 : 50 - 62
  • [30] Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees
    Blin, Lelia
    Fraigniaud, Pierre
    2015 IEEE 35th International Conference on Distributed Computing Systems, 2015, : 589 - 598
1234