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: | Ravi R., Lancia Giuseppe, Wu Bang Ye, Bafna Vineet, Chao Kun-Mao, Tang Chuan Yi |
Keywords: | biology |
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