Dynamic Steiner Tree Problem

Abstract

This paper proposes a new problem called the dynamic Steiner tree problem. Interest in the dynamic Steiner tree problem is motivated by multipoint routing in communication networks, where the set of nodes in the connection changes over time. This problem, which has its basis in the Steiner tree problem on graphs, can be divided into two cases: one in which rearrangement of existing routes is not allowed, and a second in which rearrangement is allowed. For the nonrearrangeable version, it is shown that the worst-case performance for any algorithm is at least $\frac{1}{2}\lg n$ times the cost of an optimum solution with complete rearrangement. Here n is the maximum number of nodes to be connected. In addition, a simple, polynomial time algorithm is present that has worst-case performance within two times this bound. In the rearrangeable case, a polynomial time algorithm is presented with worst-case performance bounded by a constant times optimum.