摘要
本文对图的斯坦纳问题和直角斯坦纳问题各设计了一个近似算法。算法不是以构造为主，而是先利用一简单方法构造出斯坦纳树，再用回路修改法对其进行全面改造，从而克服了以局部优化为目标的局限性。
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.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
1997年第1期53-59,共7页
Journal of Computer-Aided Design & Computer Graphics
关键词
图
斯坦纳树
直角斯坦纳树
回路修改法
网络
Steiner tree of a graph, rectilinear Steiner tree, loop modification approach.
