Simple and fast reoptimizations for the steiner tree problem
Povzetek
We address reoptimization issues for the Steiner tree problem. We assume that an optimal solution is given for some instance of the problem and the objective is to maintain a good solution when the instance is subject to minor modifications, the simplest such modifications being vertex insertions and deletions. We propose fast reoptimization strategies for the case of vertex insertions and we show that maintenance of a good solution for the 'shrunk' instance, without ex nihilo computation, is impossible when vertex deletions occur. We also provide lower bounds for the approximation ratios of the reoptimization strategies studied.
Ključne besede
reoptimizacija;Steinerjevo drevo;aproksimacijski algoritem;Steiner tree;approximation algorithms;reoptimization;
Podatki
| Jezik: | Angleški jezik |
|---|---|
| Leto izida: | 2009 |
| Tipologija: | 1.01 - Izvirni znanstveni članek |
| Organizacija: | UP - Univerza na Primorskem |
| UDK: | 519.85 |
| COBISS: |
1024188756
|
| ISSN: | Y507-0848 |
| Št. ogledov: | 2833 |
| Št. prenosov: | 26 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Neznan jezik |
|---|---|
| Sekundarne ključne besede: | Steiner tree;approximation algorithms;reoptimization; |
| Vrsta dela (COBISS): | Delo ni kategorizirano |
| Strani: | str. 86-94 |
| Letnik: | ǂVol. ǂ4 |
| Zvezek: | ǂno. ǂ2 |
| Čas izdaje: | 2009 |
| ID: | 1477158 |
Priporočena dela:
Simple and fast reoptimizations for the steiner tree problem
2009,
ni podatka o podnaslovu
Problem Steinerjevega drevesa
2017,
magistrsko delo
Vector connectivity in graphs
2014,
ni podatka o podnaslovu
Problem Steinerjevih dreves
2020,
diplomsko delo
Steiner-Wienerjev indeks grafa
2017,
delo diplomskega seminarja