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.
This work was partially supported by SBF grant C 06.0108 as part of the COST 293 (GRAAL) project funded by the European Union.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171–176 (1989)
Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Rossmanith, P.: Reoptimization of steiner trees: Changing the terminal set. Theoretical Computer Science (to appear)
Böckenhauer, H.-J., Hromkovič, J., Mömke, T., Widmayer, P.: On the hardness of reoptimization. In: 34th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2008, pp. 50–65 (2008)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1971/1972)
Escoffier, B., Milanic, M., Paschos, V.T.: Simple and fast reoptimizations for the Steiner tree problem. Technical Report 2007-01, DIMACS (2007)
Hwang, F., Richards, D., Winter, P.: The Steiner Tree Problems. Annals of Discrete Mathematics, vol. 53. North-Holland, Amsterdam (1992)
Prömel, H.J., Steger, A.: The Steiner Tree Problem. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig (2002)
Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 770–779. ACM Press, New York (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bilò, D. et al. (2008). Reoptimization of Steiner Trees. In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)