Abstract
Let G = (V,E,w) be an undirected graph with nonnegative edge weight. For any spanning tree T of G, the weight of T is the total weight of its tree edges and the routing cost of T is Σ <sub>u,v</sub> <sub>∈V</sub> dT(u,v), where dT(u,v) is the distance between u and v on T. In this paper, we present an algorithm providing a trade off among tree weight, routing cost and time complexity. For any real number a > 1 and an integer 1 ≤ k ≤ 6α-3, in O(n <sup>k</sup> <sup>+1</sup> +n <sup>3</sup> ) time, the algorithm finds a spanning tree whose routing cost is at most (1 + 2=(k + 1)) a times the one of the minimum routing cost tree, and the tree weight is at most (f(k) + 2=(α- 1)) times the one of the minimum spanning tree, where f(k) = 1 if k = 1 and f(k) = 2 if k > 1.