ABSTRACT
With different aspects, there are different measurements of the goodness of a spanning tree. For a nonnegative edge-weighted graph G, the weight on each edge represents the distance and reflects both the cost to install the link (building cost) and the cost to traverse it after the link is installed (routing cost). When considering the building cost only, we are looking for the spanning tree with minimum total weight of edges. A minimum spanning tree (MST) is an optimal solution under the consideration. When considering the routing cost only, a p-source minimum routing cost spanning tree (p-MRCT) is an optimal solution for the case of p sources. Note that a 1-MRCT is just a shortest-paths tree and a minimum routing cost spanning tree (MRCT) is for the case that all vertices are sources.
