TR#: | CS0110 |

Class: | CS |

Title: | On Finding an Optimal Communication Spanning Tree |

Authors: | Alon Itai and Michael Rodeh |

CS0110.pdf | |

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). |

Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1977/CS/CS0110), 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