Report Number: CSL-TR-76-111
Institution: Stanford University, Computer Systems Laboratory
Title: A distributed algorithm for constructing minimal spanning trees in computer-communication networks
Author: Dalal, Yogen K.
Date: June 1976
Abstract: This paper presents a distributed algorithm for constructing minimal spanning trees in computer-communication networks. The algorithm can be executed concurrently and asynchronously by the different computers of the network. This algorithm is also suitable for constructing minimal spanning trees using a multiprocessor computer system. There are many reasons for constructing minimal spanning trees in computer-communication networks since minimal spanning tree routing is useful in distributed operating systems for performing broadcast, in adaptive routing algorithms for transmitting delay estimates, and in other networks like the Packet Radio Network.
http://i.stanford.edu/pub/cstr/reports/csl/tr/76/111/CSL-TR-76-111.pdf