Abstract
Given an undirected graph with nonnegative costs on the edges, the routing cost of a pair of vertices is the cost of the shortest path between them, and the routing cost of any of its spanning trees is the sum over all pairs of vertices of the routing cost in the tree. The communication cost of a pair of vertices is its routing cost multiplied by a given requirement, and the communication cost of a spanning tree is the sum over all pairs of vertices of the communication cost in the tree. Finding a spanning tree of minimum routing cost in edge-weighted undirected general graph is known to be NP-hard, and some approximation algorithms are presented. Another problem is how to improve routing cost on any network structures using extra cost. This problem will be discussed in this thesis.