A Distributed Algorithm for Minimum Weight Directed Spanning Trees

摘要

A distributed algorithm is presented to construct minimum weight directed spanning trees (arborescences), each with a distinct root node, in a strongly connected directed graph. A processor exists at each node. Given the weights and origins of the edges incoming to its node, a processor follows the algorithm and exchanges messages with its neighbors until all arborescences are constructed. The amount of information exchanged and the time to completion are O(Absolute value of N squared).