A Distributed Algorithm for Minimum-Weight Spanning Trees

1983/01/01 by Robert G. Gallager, P.A. Humblet, Philip M. Spira · 6 citations
Computer Science · #Optimization and Search Problems #Distributed systems and fault tolerance #Complexity and Algorithms in Graphs

paper · pdf · doi:10.1145/357195.357200

openalex publication_date 1983/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/09

Abstract

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.

Citations

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Shortest Connection Networks And Some Generalizations
• Combinatorial optimization: networks and matroids
• A note on two problems in connexion with graphs

Cited by

• Implementability of Global Distributed Protocols modulo Network Architectures
• Parallel graph algorithms
• Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures
• A new approach to the maximum-flow problem
• Distributed computing [wikipedia]
• Spanning tree [wikipedia]