On-line algorithms for Steiner tree problems (extended abstract)
On-line algorithms for Steiner tree problems (extended abstract)
复制标题
Steiner 树问题的在线算法（扩展摘要）
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
C. Coulston
中科院分区：
文献类型：
--
作者：
P. Berman;C. Coulston
广义斯泰纳树问题定义如下。给定一个权重为非负的图和一组顶点对，找出最小的边网，使每对顶点都在同一个连通部分中。我们提出了在线广义斯坦纳树（GST）问题和其他两个问题的算法：直线斯泰纳解析（RSA）和对称直线斯泰纳解析（SRSA）。我们为每个问题都提供了性能比为 O(log n) 的多项式时间算法。隐藏在 O 注释中的常数因子很小，就 GST 而言，我们与已证明的下限相差不到因子 2。之前的最佳在线 GST 算法（Awerbuch 等人 [2]）是 0(log2 n)
The generalized Steiner tree problem is defined as follows. Given a graph with non-negative weights and a set of pairs of vertices find the minimum network of edges such that each pair of vertices is in the same connected component. We present an algorithm for the on-line Generalized Steiner Tree (GST) problem, and two other problems: Rectilinear Steiner Arborescence(RSA) and Symmetric Rectilinear Steiner Arborescence (SRSA). For each of these problems we provide polynomial time algorithms with performance ratios of O(log n). The constant factors hidden in the O-notation are small, in the case of the GST, we are within factor 2 from the proven lower bound. The previous best on-line GST algorithm (Awerbuch et at [2]) was 0(log2 n)