| Modifying Networks to Obtain Low Cost Trees (1998) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has an associated function Ce that specifies the cost of shortening the edge by a given amount and that there is a budget B on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint. We show that in general the problem of computing optimal reduction strategy for modifying the network as above is NP-hard and present the first polynomial time approximation algorithms for the problem, where the cost functions Ce are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are li... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||