Distributed Self-Stabilizing Algorithm for Minimum Spanning Tree Construction
Distributed Self-Stabilizing Algorithm for Minimum Spanning Tree Construction
复制标题
最小生成树构建的分布式自稳定算法
DOI：
10.1007/bfb0002773
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
P. Srimani
中科院分区：
文献类型：
--
作者：
G. Antonoiu;P. Srimani
任意无向图中的最小生成树（MST）问题是图论中的一个重要问题，具有广泛的应用。有多种算法可用于计算 MST。我们这里的目的是针对MST问题提出一种自稳定分布式算法并证明其正确性。该算法利用了 [MP88] 的一个有趣结果。我们通过使用涉及归纳的新技术来证明所提出算法的正确性。
Minimal Spanning Tree (MST) problem in an arbitrary undirected graph is an important problem in graph theory and has extensive applications. Numerous algorithms are available to compute an MST. Our purpose here is to propose a self-stabilizing distributed algorithm for the MST problem and to prove its correctness. The algorithm utilizes an interesting result of [MP88]. We show the correctness of the proposed algorithm by using a new technique involving induction.