摘要
Let G = ({1,..., n}, E, w) be an undirected graph with nonnegative edge weights w and let a <sub>ij</sub> 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 ∑ <sub>i<j</sub> a <sub>ij</sub> d <sub>H</sub> (i, j), where d <sub>H</sub> (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. © 2002 Wiley Periodicals, Inc.