Technical Report Number
This paper proposes a new problem, which we call the Dynamic Steiner Tree Problem. This is related to multipoint connection routing in communications networks, where the set of nodes to be connected changes over time. This problem can be divided into two cases, one in which rearrangement of existing routes is not allowed and a second in which rearrangement is allowed. In the first case, we show that there is no algorithm whose worst error ratio is less than 1/2 log n where n is the number of nodes to be connected. In the second case, we present an algorithm whose error rate is bounded by a constant and rearrangement is relatively small.
Imase, Makoto and Waxman, Bernard M., "Dynamic Steiner Tree Problem" Report Number: WUCS-89-11 (1989). All Computer Science and Engineering Research.