Dynamic Steiner Tree Problem
Authors:
- Makoto ImaseMIMakoto Imase
- Bernard M. WaxmanBWBernard M. Waxman
- 1 August 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 4 (3) , 369-384
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.
Keywords
This publication has 9 references indexed in Scilit:
- Competitive algorithms for on-line problems1988
- Routing of multipoint connectionsIEEE Journal on Selected Areas in Communications, 1988
- Steiner problem in networks: A surveyNetworks, 1987
- New directions in communications (or which way to the information age?)IEEE Communications Magazine, 1986
- Distributed Multi-Destination Routing: The Constraints of Local InformationSIAM Journal on Computing, 1985
- Routing to Multiple Destinations in Computer NetworksIEEE Transactions on Communications, 1983
- Graph Theory1979
- An Analysis of Several Heuristics for the Traveling Salesman ProblemSIAM Journal on Computing, 1977
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935