Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0304-3975(99)00030-4 | ICALP |
Keywords | DocType | Volume |
minimum spanning tree,spanning tree,polynomial time | Journal | 221 |
Issue | ISSN | ISBN |
1-2 | 0304-3975 | 3-540-63165-8 |
Citations | PageRank | References |
15 | 0.92 | 17 |
Authors | ||
10 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Madhav Marathe | 2 | 2775 | 262.17 |
| Hartmut Noltemeier | 3 | 398 | 97.45 |
| R. Ravi | 4 | 2898 | 275.40 |
| S. S. Ravi | 5 | 2259 | 227.21 |
| Ravi Sundaram | 6 | 762 | 72.13 |
| Hans-christoph Wirth | 7 | 146 | 15.90 |
| SO Krumke | 8 | 34 | 2.76 |
| MV Marathe | 9 | 127 | 9.05 |
| HC Wirth | 10 | 20 | 1.91 |