高磊1,张德运1,王晓东2,安智平 1
(1.西安交通大学电子与信息工程学院,710049,西安； 2.福州大学计算机科学与技术系, 350002, 福州)
摘要：针对Berman近似算法 k 为3情况下的求解思想进行了改进.在使用Fibonacci堆求解出相应点对间最短距离的基础上,通过构建Voronoi域求出元组子树的耗费,并分析了Steiner树的网络拓扑结构以去除无用元组,从而简化拓扑,降低总体时间复杂度.在实验结果中,每个实例的过滤因子均大于0.9,有的甚至高达0.999,这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉,同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效.
关键词：近似算法；拓扑分析；时间复杂度
中图分类号：TP393文献标识码：A文章编号： 0253-978x(2003)10-1012-04