An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology

In 1992 F. K. Hwang and J. F. Weng published an O(n ² ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n ² ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ). Received August 24, 1996; revised February 10, 1997.     

哈林网络中Steiner树问题的线性时间算法

设计一个在哈林网络中求解Steiner树的线性时间算法,提出伪扇的概念并在伪扇扩充至扇的过程中对Steiner树在扇中可能出现的状态进行枚举,递归压缩哈林图中的扇,通过还原所有扇得到Steiner树。算法的正确性证明、复杂度分析及应用实例分析证明,该算法对于哈林网络的多播选路具有重要的参考价值。     

Steiner Minimal Trees with One Polygonal Obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n ² +nlog ² k) time. Further, if ω is nonconvex, we then show that O(n ² +nklog k) time is required. Received April 16, 1996; revised August 18, 1997.     

On greedy heuristics for steiner minimum trees

We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to3/2. We also propose a new conjecture.Supported in part by the National Science Foundation under Grant CCR-9208913.     

一类扩展的Steiner树优化问题及其应用

本文提出了一个计算机网络通信和分布式系统中的一类扩展的Ｓｔｅｉｎｅｒ树问题．对此问题设计了两个求其最优解的算法．这两个算法的时间复杂性分别是Ｏ（３（ｋ－１）·ｎ＋２（ｋ－１）·ｎ２）和Ｏ（２（ｎ－ｋ）·ｎ２）．其中，ｋ是一棵Ｓｔｅｉｎｅｒ树需支撑的给定顶点的个数．     

Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of thebottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio √2. In this paper, the special case of the problem is proved to beNP-hard and cannot be approximated within ratio √2. First a simple polynomial time approximation algorithm with performance ratio √2 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio—√2+∈ is proposed, for any ∈>0. Supported partially by Shandong Province Excellent Middle-Aged and Young Scientists Encouragement Fund (Grant No.03BS004) and the Ministry of Education Study Abroad Returnees Research Start-up Fund, and the National Natural Science Foundation of China (Grant No.60273032).     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

延迟约束多播路由问题的分支优化算法

QoS保证下的多播服务对于许多多媒体实时应用程序是重要的,QoS约束下的多播路由协议要求寻找连接源节点和目标节点集的支撑树使得端到端的QoS约束得以满足同时优化网络资源消耗,延迟约束最小代价树DCST是其中的关键问题.本文提出一个关于DCST的分支优化算法,该算法的核心思想是通过反向分支调节过程调整不满足QoS约束的路径并且减少对原支撑树结构的影响.仿真显示本文的算法对于实际网络是有效的.     

基于拉格朗日松弛法的时延约束组播路由算法

通过对时延约束组播路由网络模型的分析,提出了一种基于拉格朗日松弛法的时延约束的低代价组播路由算法(LR-DLMR)。由于封闭图对原网络的多播不可达问题,该算法并没有构建原网络的封闭图,从而有效利用了链路中间节点信息。仿真实验结果表明本算法具有良好的稳定性,有较低的代价和时延。     

ACO-Steiner: Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm

The rectilinear Steiner minimal tree （RSMT） problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization （ACO）. An RSMT is constructed with ants＇ movements in Hanan grid, and then the constraint of Hanan grid is broken to accelerate ants＇ movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, GeoSteiner 3.1 and a recent heuristic using batched greedy triple construction （BGTC）. Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, it is Mso found that the ACO-Steiner can be easily extended to be used to some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in global routing.