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

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

欧氏平面快速k-瓶颈斯坦纳树近似算法

瓶颈k-Steiner树问题描述如下:给定n个点和一个正整数k,寻找一棵Steiner树用至多k个Steiner点将n个点连接起来,使得此Steiner树的最长边最短。L.Wang和D.-Z.Du证明了适用于欧几里得平面瓶颈斯坦纳树算法的近似性能比为2,并且给出了一个适用于该问题时间复杂度为(nlogn+kn)的算法,在欧几里得平面上和近似性能比为2的前提下,通过引入最大堆和斐波那契堆分别对该算法进行优化,优化后算法的时间复杂度分别达到(nlogn+klogn)和(nlogn+k),优化后的算法在现实中可以更好地应用。