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