A self-stabilizing 2-minimal dominating set algorithm based on loop composition in networks of girth at least 7
A self-stabilizing 2-minimal dominating set algorithm based on loop composition in networks of girth at least 7
复制标题
周长至少为 7 的网络中基于循环组合的自稳定 2 最小支配集算法
DOI：
10.1109/ipdps53621.2022.00114
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kakugawa Hirotsugu
中科院分区：
文献类型：
--
作者：
Maruyama Syohei;Sudo Yuichi;Kamei Sayaka;Kakugawa Hirotsugu
本文提出了一个在围长至少为7的网络中寻找2-极小支配集（2-MDS）的无声自稳定异步分布式算法。给定一个图，的2-MDS是一个极小控制集，使得它对任何结点都不是控制集。围长是图中最短圈的长度。我们假设进程有唯一的标识符。该算法在弱公平分布式守护进程下，在围长至少为7的网络中构造了一个2-MDS。时间复杂度为四舍五入，空间复杂度为每进程位数，其中是进程数，是网络直径。
We propose a silent self-stabilizing asynchronous distributed algorithm to find a 2-minimal dominating set (2-MDS) in networks of girth at least 7. Given a graph, a 2-MDS ofis a minimal dominating setsuch thatis not a dominating set for any nodesand. The girth is the length of the shortest cycles in the graph. We assume that the processes have unique identifiers. The proposed algorithm constructs a 2-MDS in the networks of girth at least 7 under the weakly fair distributed daemon. The time complexity isrounds, and the space complexity isbits per process, whereis the number of processes andis the diameter of the network.