改进的基于拓扑分析的Steiner树近似算法

• 作者: 安智平 张德运 王晓东 高磊
• 来源期刊: 西安交通大学学报
• 关键词: 近似算法 拓扑分析 时间复杂度
• 年，卷（期）: 2003,（10）
• 页码范围: 1012-1015
• 页数: 4页
• 分类号: TP393
• 语种: 中文
• DOI: 10.3321/j.issn:0253-987X.2003.10.006

摘要

针对Berman近似算法k为3情况下的求解思想进行了改进.在使用Fibonacci堆求解出相应点对间最短距离的基础上,通过构建Voronoi域求出元组子树的耗费,并分析了Steiner树的网络拓扑结构以去除无用元组,从而简化拓扑,降低总体时间复杂度.在实验结果中,每个实例的过滤因子均大于0.9,有的甚至高达0.999,这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉,同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张德运	西安交通大学电子与信息工程学院	184	2190	23.0	37.0
2	高磊	西安交通大学电子与信息工程学院	41	174	8.0	11.0
3	安智平	西安交通大学电子与信息工程学院	11	84	6.0	8.0
4	王晓东	福州大学计算机科学与技术系	66	432	14.0	17.0