Email RIS file
Bookmark
Report an Issue

Improving spanning trees by upgrading nodes [electronic resource].

Published
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, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Free-to-read Unrestricted online access
Summary
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.
Report Numbers
E 1.99:la-ur--97-476
E 1.99: conf-970746--1
conf-970746--1
la-ur--97-476
Subject(s)
Other Subject(s)
Note
Published through SciTech Connect.
01/16/1997.
"la-ur--97-476"
" conf-970746--1"
"DE97004796"
International colloquium on automata, language and programming, Bologna (Italy), Jul 1997.
Wirth, H.C.; Krumke, S.O.; Noltemeier, H.
Funding Information
W-7405-ENG-36
View MARC record | catkey: 14349252