Reoptimization for Steiner tree problem Adding and deleting an edge

It is well known that Steiner tree problem is one of the famous NP hard problem of combinatorial optimization. In this paper, we address the problem of reoptimization of Steiner trees. An optimal Steiner tree corresponding to a given weighted graph and a set of terminal nodes is known. If there is a small change in the given graph such as addition and deletion of node/edge, objective is to maintain a good Steiner tree without re-computing it from the scratch. Algorithms to generate near optimal solution after addition and deletion of node/edge have already been proposed. These algorithms do not cover all possible cases so they are not correct in a general sense. Here we propose two algorithms ADDEDGE and DELETE EDGE by doing some modifications in the existing algorithms EDGEADD and EDGEREMOVE to get better (more closer to optimal) solution and also covering those cases which were not covered earlier.