A DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING-TREES
A DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING-TREES
复制标题
DOI：
10.1145/357195.357200
复制
发表时间：
1983-01-01
影响因子：
1.3
通讯作者：
SPIRA, PM
中科院分区：
文献类型：
--
作者：
GALLAGER, RG;HUMBLET, PA;SPIRA, PM
提出了一种在具有不同边权的连通无向图中构造最小权生成树的分布式算法。处理器存在于图的每个节点处，最初仅知道相邻边的权重。处理器遵循相同的算法，并与邻居交换消息，直到树被构建。一个由N个节点和E条边组成的图所需的消息总数最多为5N log2N +2E，并且一个消息最多包含一个边权重加上log28N比特。该算法可以在任何节点或节点的任何子集处自发地发起。
A distributed algorithm is presented that constructs the minimum-weight spanning tree in a connected undirected graph with distinct edge weights. A processor exists at each node of the graph, knowing initially only the weights of the adjacent edges. The processors obey the same algorithm and exchange messages with neighbors until the tree is constructed. The total number of messages required for a graph of N nodes and E edges is at most 5N log2N+ 2E, and a message contains at most one edge weight plus log28N bits. The algorithm can be initiated spontaneously at any node or at any subset of nodes.