| Improving Spanning Trees by Upgrading Nodes (1998) | |||||||||||||||
Abstract | |||||||||||||||
| Id: upgrade.tex,v 2.2 1997#09#18 13:14:08 krumke Exp wirth We study bottleneck constrained network upgrading problems.We are given an edge weighted graph G =#V;E# where node v 2 V can be upgraded at a cost of c#v#. This upgrade reduces the delayofeach link emanating from v. The goal is to #nd a minimum cost set of nodes to be upgraded so that the resulting network has a good performance. The performance is measured by the bottleneckweightof a minimum spanning tree. We give a polynomial time appoximation algorithm with logarithmic performance guarantee, which is tight within a small constant factor as shown by our hardness results. Preprint submitted to Elsevier Preprint 24 September 1997 Key words: NP-hardness, Approximation Algorithms, Network Design, Spanning-Tree. 1 Introduction Several problems arising in areas such as communication networks can be expressed in the following general form: Enhance the performance of an underlying network by carrying out upgrades at certain ... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||