| Upgrading Bottleneck Constrained Forests (1998) | |||||||||||||||||
Abstract | |||||||||||||||||
| . 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 delay of each link emanating from v. The goal is to find a minimum cost set of nodes to be upgraded so that the resulting network has a good performance. The performance is measured by the bottleneck weight of a constrained forest defined by a proper function [GW92]. These problems are a generalization of the node weighted constrained forest problems studied by Klein and Ravi [KR93]. The main result of the paper is a polynomial time approximation algorithm for this problem with performance guarantee of 2 ln( p e=2 Delta jKj), where K := f v : f(fvg) = 1 g is the set of terminals given by the proper function f . We also prove that the performance bound is tight up to small constant factors by providing a lower bound of ln jKj. Our results are obtained by extending the elegant solution ba... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||