A polynomial-time approximation scheme for minimum routing cost spanning trees

A polynomial-time approximation scheme for minimum routing cost spanning trees

0.00 Avg rating0 Votes
Article ID: iaor20011998
Country: United States
Volume: 29
Issue: 3
Start Page Number: 761
End Page Number: 778
Publication Date: Jan 2000
Journal: SIAM Journal On Computing
Authors: , , , , ,
Keywords: biology
Abstract:

Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the tree. Finding a spanning tree of minimum routing cost is NP-hard, even when the costs obey the triangle inequality. We show that the general case is in fact reducible to the metric case and present a polynomial-time approximation scheme valid for both versions of the problem. In particular, we show how to build a spanning tree of an n-vertex weighted graph with routing cost at most (1 + ε) of the minimum in time O(nO(1/ε)). 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. The communication cost spanning tree problem is a generalization of the minimum routing cost tree problem where the routing costs of different pairs are weighted by different requirement amounts. We observe that a randomized O(log n log log n)-approximation for this problem follows directly from a recent result of Bartal, where n is the number of nodes in a metric graph. This also yields the same approximation for the generalized sum-of-pairs alignment problem in computational biology.

Reviews

Required fields are marked *. Your email address will not be published.