Faster Approximation Algorithm For K-bottleneck Steiner Tree

Traditional Steiner tree problem has wide application in the fields of very large scale integrated circuit design,computer network construction,IC chip routing,wireless communication network design and reconstruction of evolutionary tree.Recent emerging new applications trigger the modification of the traditional Steiner tree problem and thus the study of variants of Steiner tree problem has important significance.Currently,variants of the traditional Steiner tree problem includes the k-bottleneck Steiner tree problem and the Steiner tree problem with minimum Steiner points under limited maximum edge length.The main content of this dissertation is the study of k-bottleneck Steiner tree problem in both Euclidean and Rectilinear plane,specific content as follows:(1)Started from the basic theory of Steiner tree problem,the dissertation describes the notion,application and variation of Steiner tree problem,and presents the L.Wang and D-Z.Du's approximation algorithm with performance ratio 2 and analyzed its time complexity in details.(2)Improvement of the time complexity of the L.Wang and D-Z.Du's algorithm.By introducing the binary heap and Fibonacci heap,we improve the time complexity of the L.Wang and D-Z.Du's 2-approximation algorithm from the actual time O(nlogn + kn + k2)to O(nlogn + klogn)and amortized time O(nlogn + klogn),respectively.(3)Implementation of the above algorithms shows the high efficiencies of new algorithms when the number of the given points and the number of Steiner points is changed.In the last,this dissertation summarizes the main work,and propose the prospect of the next phase of the Steiner tree problem.