摘要
关于图的Steiner树问题的研究,近年来已有些新的进展．本文给出时间复杂度为O(nlogn+m) 的新算法,使该求解问题的算法在时间复杂度上又有较大改进．这里n=|v|是连通无向图G=(V,E) 的结点,M=|E|是其边数．
It has been developed recently to study the Steiner Tree Problem in Graphs. Inthis Paper we develop a new approximation algorithm which has a time complexity of O(nlogn+m), whee n = |V| is the number of vertices in a connected and directed graphG = (V, E), M =|E| is the number of edges in G. This is a greater improvment upon thisproblem.
出处
《黑龙江大学自然科学学报》
CAS
1991年第2期60-64,共5页
Journal of Natural Science of Heilongjiang University
关键词
STEINER树
有效算法
时间复杂度
Steiner tree
efficient algorithm
approximation algorithm
time complexity
fibonacci heap
minimum spanning tree.
