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

• 作者: 李子茂 李晓丹
• 来源期刊: 中南民族大学学报（自然科学版）
• 学科: 工学
• 关键词: 瓶颈斯坦纳树 近似算法 性能比 无线通讯网络
• 年，卷（期）: 2016,（3）
• 所属期刊栏目: 计算机科学
• 页码范围: 97-101
• 页数: 5页
• 分类号: TP312
• 字数: 1163字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李子茂	中南民族大学计算机科学学院	13	31	3.0	5.0
2	李晓丹	中南民族大学计算机科学学院	2	0	0.0	0.0