Tang, Chuan Yi
Ravi, R.
Chao, Kun-Mao
Bafna, Vineet
Lancia, Giuseppe
Wu, Bang Ye
Abstract
| 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 + epsilon) of the the minimum in time O(n ^ O(1/epsilon)).
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.
|
Keywords
tree
spanning tree
routing cost
Notes
| Important. Shows how to build a bounded cost spanning tree if a fixed amount
of time.
|
Related Papers
Bibtex
@article{wu.tang_poly98,
author = "B. Y. Wu and G. Lancia and V. Bafna and K. M. Chao and R. Ravi and C. Y. Tang",
title = "A polynomial time approximation scheme for minimum routing cost spanning trees",
journal="SIAM Journal on Computing",
number="3",
volume="29",
pages="761--778",
year="2000"
}