Improving spanning trees by upgrading nodes [electronic resource].
- Washington, D.C. : United States. Dept. of Energy, 1997.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
- Physical Description:
- 19 pages : digital, PDF file
- Additional Creators:
- Los Alamos National Laboratory
United States. Department of Energy
United States. Department of Energy. Office of Scientific and Technical Information
- We study budget constrained optimal network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. A general problem in this setting is the following. We are given an edge weighted graph G = (V, E) where nodes represent processors and edges represent bidirectional communication links. The processor at a node v ∈ V can be upgraded at a cost of c(v). Such an 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 the best performance with respect to some measure. We consider the problem under two measures, namely, the weight of a minimum spanning tree and the bottleneck weight of a minimum bottleneck spanning tree. We present approximation and hardness results for the problem. Our results are tight to within constant factors. We also show that these approximation algorithms can be used to construct good approximation algorithms for the dual versions of the problems where there is a budget constraint on the upgrading cost and the objectives are minimum weight spanning tree and minimum bottleneck weight spanning tree respectively.
- Published through SciTech Connect.
International colloquium on automata, language and programming, Bologna (Italy), Jul 1997.
Wirth, H.C.; Krumke, S.O.; Noltemeier, H.
- Funding Information:
View MARC record | catkey: 14349252