|
|||||
|
|
| 网格空间瓶颈斯坦纳树问题快速近似（英文） | |
| 作者单位： | ;1.中南民族大学计算机科学学院 |
| 摘 要： | 指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法. |
| 关 键 词： | 瓶颈斯坦纳树 近似算法 性能比 无线通讯网络 |
Faster Approximation for Rectilinear Bottleneck Steiner Tree Problem |
|
| Abstract: | |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ | |