MINIMIZING THE DIAMETER IN TREE NETWORKS UNDER EDGE REDUCTIONS

Edge reductions model the ability of speeding up communication between processors in a network. In this paper we consider performing edge reductions in a tree network so that the diameter of the tree is minimized. The diameter is directly related to the time needed to broadcast a message. In particular, for non-blocking message communication ignoring start-up costs, the diameter corresponds to the broadcasting time. For an n-vertex tree T and a quantity B, we present an O(n) time algorithm to determine edge reductions such that the resulting tree has diameter at most B and the cost of the reduction is a minimum (over all reductions resulting in a diameter of at most B).