Technical Report CS0110

Title: On Finding an Optimal Communication Spanning Tree
Authors: Alon Itai and Michael Rodeh
Abstract: An optimum communication spanning tree of an undirected graph is a spanning tree which minimizes the sum of the lengths of the tree paths between all pairs of vertices. It is shown that finding an optimal communication spanning tree is ~P-comp1ete. The maximum communication cost of a spanning tree of an n-vertex graph is o(n^3) . The average cost over all trees is 0(n^5/2). The maximum cost of a breadth first search tree may be worse than the cost of an optimum tree by a factor of at most n^2/3. For n sufficiently large, ,l+1og/loglogn bounds the diameter of most n-vertex graphs, in which the appearance of an edge is an independent random variable with probability P>=16 logn/n. Therefore, the communication cost of a breadth-first-search tree on such graphs is bounded by O(n^2*1ogn/loglogn).
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 1977
To the main CS technical reports page

Computer science department, Technion