Light graphs with small routing cost
Let G = ({1,..., n}, E, w) bean undirected graph with nonnegative edge weights w and let a(ij) be the nonnegative requirement between vertices i and j. For any spanning subgraph H of G, the weight of H is the total weight of its edges and the routing cost of H is Sigma(i<j) a(ij)d(H)(i, j), where d(H)(i, j) is the distance between i and j in H. In this paper, we investigated two special cases of the problem of finding a spanning subgraph with small weight and small routing cost. For the case where all the distances in G are 1, we show that the problem is NP-complete, and give a simple approximation algorithm for it. Furthermore, we define some sufficient conditions for the problem to be polynomial-time solvable. For the case where all the requirements are 1, we develop an algorithm for finding a spanning tree with small weight and small routing cost. The algorithm provides trade-offs among tree weights, routing costs, and time complexity. We also extend the results to some other related problems. (C) 2002 Wiley Periodicals, Inc.
approximation algorithms spanning trees network design