网格空间瓶颈斯坦纳树问题快速近似（英文）

Faster Approximation for Rectilinear Bottleneck Steiner Tree Problem

指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法.

Bottleneck Steiner tree problem asks to find a Steiner tree for n terminals with at most k Steiner points such that the length of the longest edge in the tree is minimized. The problem has applications in VLSI routing, wireless communication networks and phylogenetic tree reconstruction. Du and Wang showed that the rectilinear bottleneck Steiner problem is NP-hard and cannot be approximated within performance ratio 2 in polynomial time, and provided a 2- approximation algorithm running in actual timeO （n lo g 2n ＋ kn ＋ k^2） . In this paper w e improve the algorithm＇s time complexity to O（nlog2n ＋ klog2n） and armotized O（nlog 2n ＋ klog2n） , by introducing the binary heap and Fibonacci heap respectively. The improvement can be directly applied to their Euclidean bottleneck Steiner tree problem^＇s2-approximation algorithm.