Abstract
For 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 the pair, 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. Besides the obvious connection to network design, trees with small routing cost also find application in the construction of good multiple sequence alignments in computational biology. For finding the minimum routing cost spanning tree (MRCT), several approximation algorithms achieving constant ratios are shown. Then, it is shown that the problem admits a PTAS. The communication cost of a pair of vertices is its routing ost 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. Two vertex-weighted generalizations of the MRCT problem are considered. For the PROCT problem, the routing requirement of any pair of vertices is defined as the product of the vertex weights, and the goal is to find the spanning tree with minimum communication cost. For the SROCT problem, the requirement is defined as the sum of the vertex weights. A 1.577-approximation algorithm for the PROCT is first presented. Then, by a new technique called scaling and rounding, the problem is shown to admit a PTAS. For the SROCT problem, a 2-approximation algorithm is presented. Another problem is how to find a spanning tree with small routing cost and small total weight of its tree edges. An algorithm providing a trade off among tree weight, routing cost and time complexity is presented. The result is also extended to several related problems and approximation algorithms are obtained.