A Distributed Algorithm for Minimum-Weight Spanning Trees
Robert G. Gallager, P.A. Humblet, Philip M. Spira · ACM Transactions on Programming Languages and Systems · 1983
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.
Cited by 1,129 works. doi:10.1145/357195.357200 Open-access PDF
Authors
References
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A note on two problems in connexion with graphs
- Shortest Connection Networks And Some Generalizations
- Combinatorial optimization: networks and matroids
- INTRODUCTION TO COMBINATORIAL MATHEMATICS
- Introduction to Combinatorial Mathematics.
- Broadcast protocols in packet switched computer networks
- An 0(|E|loglog|V|) algorithm for finding minimum spanning trees
- A Distributed Algorithm for Minimum Weight Directed Spanning Trees
- Communication Complexity of Distributed Minimum Spanning Tree Algorithms.