Improving spanning trees by upgrading nodes

We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V, E) where node upsilon is an element of V can b e upgraded at a cost of c(upsilon), This upgrade reduces the delay of each link emanating from v. The goal is to find a minimum cost set of nodes to b e upgraded so that the resulting network has good performance. The performa nce is measured by the bottleneck weight of a minimum spanning tree. We give a polynomial time approximation algorithm with logarithmic performa nce guarantee, which is tight within a small constant factor as shown by ou r hardness results. (C) 1999 Published by Elsevier Science B.V. All rights reserved.