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 条
  • [1] Self-stabilizing algorithms for efficient sets of graphs and trees
    Turau, Volker
    INFORMATION PROCESSING LETTERS, 2013, 113 (19-21) : 771 - 776
  • [2] New Self-Stabilizing Algorithms for Minimal Weakly Connected Dominating Sets
    Ding, Yihua
    Wang, James Z.
    Srimani, Pradip K.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2015, 26 (02) : 229 - 240
  • [3] Self-stabilizing algorithms for minimal global powerful alliance sets in graphs
    Yahiaoui, Said
    Belhoul, Yacine
    Haddad, Mohammed
    Kheddouci, Hamamache
    INFORMATION PROCESSING LETTERS, 2013, 113 (10-11) : 365 - 370
  • [4] Self-stabilizing algorithm for two disjoint minimal dominating sets
    Srimani, Pradip K.
    Wang, James Z.
    INFORMATION PROCESSING LETTERS, 2019, 147 : 38 - 43
  • [5] An O(n2) Self-Stabilizing Algorithm for Minimal Total Dominating Set in Arbitrary Graphs
    Ding, Yihua
    Wang, James Z.
    Srimani, Pradip K.
    2020 IEEE/WIC/ACM INTERNATIONAL JOINT CONFERENCE ON WEB INTELLIGENCE AND INTELLIGENT AGENT TECHNOLOGY (WI-IAT 2020), 2020, : 49 - 54
  • [6] A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
    Turau, Volker
    Hauck, Bernd
    INFORMATION PROCESSING LETTERS, 2009, 109 (14) : 763 - 767
  • [7] A self-stabilizing algorithm for optimally efficient sets in graphs
    Hedetniemi, Sandra M.
    Hedetniemi, Stephen T.
    Jiang, Hao
    Kennedy, K. E.
    McRae, Alice A.
    INFORMATION PROCESSING LETTERS, 2012, 112 (16) : 621 - 623
  • [8] A Linear Time Self-stabilizing Algorithm for Minimal Weakly Connected Dominating Sets
    Ding, Yihua
    Wang, James Z.
    Srimani, Pradip K.
    INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, 2016, 44 (01) : 151 - 162
  • [9] A distributed algorithm to find k-dominating sets
    Penso, LD
    Barbosa, VC
    DISCRETE APPLIED MATHEMATICS, 2004, 141 (1-3) : 243 - 253
  • [10] A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
    Guellati, Nabil
    Kheddouci, Hamamache
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2010, 70 (04) : 406 - 415
1234