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

作　　者：李晓丹[1] 

机构地区：[1]中南民族大学计算机科学学院,武汉430074

出　　处：《电脑编程技巧与维护》2016年第6期31-34,共4页Computer Programming Skills & Maintenance

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

关 键 词：瓶颈斯坦纳树 时间复杂度 最大堆 斐波那契堆 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]