Technical Report CS0334

Title: The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
Authors: E. Korach, S. Moran and S. Zaks
Abstract: In a previous paper it was shown that the distributive construction of a spanning tree in a complete network of processors can be done in O(nlogn) messages. We show in this work that if the spanning tree is required to satisfy certain properties, then the complexity of its construction increases: First we show that the construction of a minimum weight spanning tree requires, in the worst case, O(n^2) messages, and then we show that the construction of a spanning tree where the maximum degree is at most k may require O{n^2/k) messages in the worst case. The validity of the results is independent of the length of the messages used. On the other hand, there are algorithms for the above tasks which achieve these lower bounds, up to a constant factor, and use messages of O(logn) length.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion