Improving spanning trees by upgrading nodes

被引：13

作者：

Krumke, SO

Noltemeier, H

Wirth, HC

Marathe, MV

Ravi, R

Ravi, SS

Sundaram, R

机构：

[1] Konrad Zuse Zentrum Informat Tech Berlin ZIB, D-14195 Berlin, Germany

[2] Univ Wurzburg, Dept Comp Sci, D-97074 Wurzburg, Germany

[3] Los Alamos Natl Lab, Los Alamos, NM 87545 USA

[4] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA

[5] SUNY Albany, Dept Comp Sci, Albany, NY 12222 USA

[6] MIT, Cambridge, MA 02139 USA

来源：

THEORETICAL COMPUTER SCIENCE | 1999年 / 221卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

NP-hardness; approximation algorithms; network design; spanning tree;

D O I：

10.1016/S0304-3975(99)00030-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V, E) where node upsilon is an element of V can be upgraded at a cost of c(upsilon), 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 good performance. The performance is measured by the bottleneck weight of a minimum spanning tree. We give a polynomial time approximation algorithm with logarithmic performance guarantee, which is tight within a small constant factor as shown by our hardness results. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：139 / 155

页数：17

共 13 条

[1] AN ALGEBRAIC-THEORY OF GRAPH REDUCTION [J].