28 A DISTRIBUTED SYNCHRONOUS ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES

Abstract: This paper presents a distributed synchronous algorithm for constructing the Minimum-Weight Spanning Tree (MST) in a connected undirected graph with distinct edge weights. Each node in the graph is considered as a processor having the initial knowledge of weights of the adjacent edges and each edge is considered as communication link. Each processor executes the same synchronous algorithm and exchanges the messages with the neighbours until the complete MST is formed. This algorithm constructs the fragments of MST and these fragments are then combined to form the complete MST. The total number of messages required for N processors and E communication links is O(N