| 两种斯坦纳问题的近似算法 |
| |
| 引用本文： | 宋学军 纪玉波. 两种斯坦纳问题的近似算法[J]. 计算机辅助设计与图形学学报, 1997, 9(1): 53-59 |
| |
| 作者姓名： | 宋学军 纪玉波 |
| |
| 作者单位： | 天津大学电力及自动化工程系，抚顺石油学院计算机系 |
| |
| 摘 要： | 本文对图的斯坦纳问题和直角斯坦纳问题各设计了一个近似算法。
|
| 关 键 词： | 图 斯坦纳树 直角斯坦纳树 回路修改法 网络 |
APPROXIMATION ALGORITHMS FOR TWO KINDS OF STEINER PROBLEMS |
| |
| Abstract: | Approximation algorithms for the Steiner Problem in graphs and the rectilinear Steiner problem are presented respectively. These algorithms are not based on constructing the resulting tree step by step. Instead, they get an initial tree at first by a simple way and then concentrate on thoroughly refining it by a loop modification approach. Limitations of aiming at local optimization can be avoided. The results are near global optimum and the algorithms are of low time and space complexity. |
| |
| Keywords: | Steiner tree of a graph rectilinear Steiner tree loop modification approach. |
| 本文献已被 CNKI 维普 等数据库收录！ |
