摘要
Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1 + 2 / ( α - 1 ) times of that of an MST of G, and the k-source routing cost of T is at most α ( 1 + 2 ( k - 1 ) ( n - 2 ) / k ( n + k - 2 ) ) times of that of a k-MRCT of G with respect to S, where α > 1, k = | S | and n is the number of vertices of G. © 2006 Elsevier B.V. All rights reserved.