SIAM Journal on Discrete Mathematics · 1991 · 361 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsComputer NetworksOptimizationCombinatorial OptimizationGraph AlgorithmsNetwork OptimizationNetwork TopologyRoutingRouting AlgorithmsDynamic Communication NetworksPolynomial-time AlgorithmsRouting ProblemsSteiner Tree ProblemWorst-case ComplexityWorst-case Optimization
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.
7
Routing of multipoint connections
Bernard M. Waxman · IEEE Journal on Selected Areas in Communications · 1988 · 2.9K citations
P. Hall · Journal of the London Mathematical Society · 1935 · 2K citations
Steiner problem in networks: A survey
Paweł Winter · Networks · 1987 · 594 citations