Title :
Fast reoptimization of Steiner trees
Author :
Panwar, Subhash ; Agarwaal, Suneeta
Author_Institution :
Comput. Sci. & Eng. Dept., Motilal Nehru Nat. Inst. of Technol., Allahabad, India
Abstract :
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 occur later on in the given graph, a new optimal Steiner tree is to be determined. 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 from the given graph. For both the cases, we provide approximation algorithms with corresponding approximation ratio equal to (1 + ¿) where 0 < ¿ < 1.
Keywords :
approximation theory; optimisation; trees (mathematics); Steiner tree reoptimization; approximation algorithm; graph; Algorithm design and analysis; Approximation algorithms; Approximation methods; Computer science; Costs; Design optimization; Joining processes; Steiner trees; Tree graphs; Approximation algorithm; Reoptimization; Steiner tree;
Conference_Titel :
Advance Computing Conference (IACC), 2010 IEEE 2nd International
Conference_Location :
Patiala
Print_ISBN :
978-1-4244-4790-9
Electronic_ISBN :
978-1-4244-4791-6
DOI :
10.1109/IADCC.2010.5423050
