| 改进的基于拓扑分析的Steiner树近似算法 |
| |
| 引用本文： | 高磊,张德运,王晓东,安智平. 改进的基于拓扑分析的Steiner树近似算法[J]. 西安交通大学学报, 2003, 37(10): 1012-1015 |
| |
| 作者姓名： | 高磊 张德运 王晓东 安智平 |
| |
| 作者单位： | 1. 西安交通大学电子与信息工程学院,710049,西安
2. 福州大学计算机科学与技术系,350002,福州 |
| |
| 基金项目： | 国家“八六三”计划资助项目 (863 3 0 1 5 3 ) |
| |
| 摘 要： | 针对Berman近似算法k为3情况下的求解思想进行了改进。在使用Fibonacci堆求解出相应点对间最短距离的基础上，通过构建Voronoi域求出元组子树的耗费，并分析了Steiner树的网络拓扑结构以去除无用元组，从而简化拓扑，降低总体时间复杂度。在实验结果中，每个实例的过滤因子均大于0．9，有的甚至高达0．999，这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉，同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效。
|
| 关 键 词： | 近似算法 拓扑分析 时间复杂度 |
| 文章编号： | 0253-987X(2003)10-1012-04 |
| 修稿时间： | 2002-12-18 |
Improved Approximation Algorithm for Steiner Tree Based on Topology Analysis |
| |
| Abstract: | |
| |
| Keywords: | approximation algorithm topology analysis time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
