Document Type
Technical Report
Publication Date
1989-03-01
Technical Report Number
WUCS-89-11
Abstract
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.
Recommended Citation
Imase, Makoto and Waxman, Bernard M., "Dynamic Steiner Tree Problem" Report Number: WUCS-89-11 (1989). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/724
Comments
Permanent URL: http://dx.doi.org/10.7936/K7X34VST