Abstract
Let G = (V,E,w) be an undirected graph with nonnegative edge weight w, and r be a nonnegative vertex weight. The product-requirement optimum communication spanning tree (PROCT) problem is to find a spanning tree T minimizing Σ i,j∈v r(i)r(j)d(T,i,j), where d(T, i, j) is the distance between i and j on T. The sum-requirement optimum communication spanning tree (SROCT) problem is to minimize Σ i,j∈ (r(i) + r(j))d(T,i,j). Both the two problems are special cases of the general optimum communication spanning tree problem, and are generalizations of the shortest total path length spanning tree problem. In this paper, we present an O(n 5 ) time 1.577-approximation algorithm for the PROCT problem, and anO(n 3 ) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices. © Springer-Verlag Berlin Heidelberg 1998.