Improving spanning trees by upgrading nodes
| Autor: | Madhav V. Marathe, Hans-C. Wirth, S. S. Ravi, R. Ravi, Ravi Sundaram, Sven O. Krumke, Hartmut Noltemeier |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Mathematical optimization
Spanning tree General Computer Science Minimum bottleneck spanning tree Node (networking) Approximation algorithm Graph theory Minimum spanning tree Steiner tree problem Approximation algorithms Bottleneck Theoretical Computer Science symbols.namesake NP-hardness symbols Physics::Accelerator Physics Network design Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 221(1-2):139-155 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(99)00030-4 |
| Popis: | We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V,E) where node ν ε V can be upgraded at a cost of c(ν). This upgrade reduces the delay of each link emanating from ν. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect