An Incremental Algorithm for (2-ε)-Approximate Steiner Tree Requiring O(n) Update Time

Given an undirected connected weighted graph with non-negative edge weights and a subset of vertices called terminals, the goal of the Steiner tree problem is to find a tree that spans the terminals such that the weight of the tree is minimized. A dynamic graph is a graph where the edge set or the vertex set or both may change with time. In this paper, first, we give a lower bound on the worst case update time for maintaining a(2-$\epsilon$)-approximate Steiner tree ($\epsilon$ being a small fraction) based on MST heuristic in a general dynamic graph with edge insertions and deletions. Then we propose an incremental algorithm for the Steiner tree problem in general dynamic graphs with edge insertions. We consider a weighted undirected connected graph with positive real edge weights and each update inserts an edge with a specific weight in the graph. The goal is to maintain a Steiner tree of the terminals. The algorithm maintains a(2-$\epsilon$)-approximate Steiner tree in O(n) update time where n is the number of vertices in the graph.