ABSTRACT

The optimal communication spanning tree (OCT) problem is defined as follows. Let G = (V, E, w) be an undirected graph with nonnegative edge length function w. We are also given the requirements λ(u, v) for each pair of vertices. For any spanning tree T of G, the communication cost between two vertices is defined to be the requirement multiplied by the path length of the two vertices on T , and the communication cost of T is the total communication cost summed over all pairs of vertices. Our goal is to construct a spanning tree with minimum communication cost. That is, we want to find a spanning tree T such that

∑ u,v∈V λ(u, v)dT (u, v) is minimized.