Document Type

Technical Report

Publication Date

1989-03-01

Filename

WUCS-89-11.pdf

DOI:

10.7936/K7X34VST

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7X34VST

Download

Share

COinS