Approximation algorithms for some optimum communication spanning tree problems

Let G = (V,E,w) be an undirected graph with nonnegative edge length functio n w and nonnegative vertex weight function,. The optimal product-requiremen t communication spanning tree (PROCT) problem is to find a spanning tree T minimizing Sigma(u,v is an element of V) r(u)r(v)d(T)(u,v), where d(T)(u,v) is the length of the path between u and v on T. The optimal sum-requiremen t communication spanning tree (SROCT) problem is to find a spanning tree T such that Sigma(u,v is an element of V) (r(u) + r(v))d(T)(u,v) is minimized . Both problems are special cases of the optimum communication spanning tre e problem, and are reduced to the minimum routing cost spanning tree (MRCT) problem when all the vertex weights are equal to each other. In this paper , we present an O(n(5))-time 1.577-approximation algorithm for the PROCT pr oblem, and an O(n(3)) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices. We also show that a 1.577-approximation solution for the MRCT problem can be obtained in O(n(3))-time, which impro ves the time complexity of the previous result. (C) 2000 Elsevier Science B .V. All rights reserved.