DYNAMIC STEINER TREE PROBLEM

作     者：IMASE, M WAXMAN, BM 

作者机构：SO ILLINOIS UNIV DEPT COMP SCI EDWARDSVILLE IL 62026 USA 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1991年第4卷第3期

页      面：369-384页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：STEINER TREE PROBLEM MULTIPOINT CONNECTION MULTIPOINT ROUTING APPROXIMATION ALGORITHM WORST CASE COMMUNICATION NETWORKS 

摘      要：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 1/2 lg n times the cost of an optimum solution with complete rearrnagement. Here n is the maximum number of nodes to be connected. In addition, a simple, polynomial time 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 time optimum.