Fast reoptimization of Steiner trees: Changing the Edge set
Subhash Panwar, Suneeta Agarwal · International Journal of Computer Applications · 2010
In this paper, we discuss the problem of reoptimization of Steiner tree.We are given an instance of Graph and also an optimal Steiner tree of it.If some changes occurs later on in the given graph.New optimal Steiner tree is to be determine, this process is known as re optimization.We consider two cases of change: one is addition of a new edge and second is, Deletion of an existing edge.For both the cases, we provide approximation algorithms with corresponding approximation ratio equal to (1+δ) where 0<δ<1.