Data di Pubblicazione:
2008
Citazione:
Reoptimization of Steiner Trees / Bilò, Davide; BÖCKENHAUER HANS, Joachim; Hromkovic, Juraj; Královic, Richard; Mömke, Tobias; Widmayer, Peter; Zych, Anna. - 5124:(2008), pp. 258-269. ( 11th Scandivian Workshop on Algorithm Theory (SWAT 2008) Gothenburg, Sweden July 2-4, 2008) [10.1007/978-3-540-69903-3_24].
Abstract:
In this paper we study the problem of finding a minimum Steiner Tree given a minimum Steiner Tree for similar problem instance. We consider scenarios of altering an instance by locally changing the terminal set or the weight of an edge. For all modification scenarios we provide approximation algorithms that improve best currently known corresponding approximation ratios.
Tipologia CRIS:
4.1 Contributo in Atti di convegno
Elenco autori:
Bilò, Davide; BÖCKENHAUER HANS, Joachim; Hromkovic, Juraj; Královic, Richard; Mömke, Tobias; Widmayer, Peter; Zych, Anna
Link alla scheda completa:
Titolo del libro:
Algorithm Theory - SWAT 2008
Pubblicato in: