An optimal algorithm for the Euclidean bottleneck full Steiner tree problem

作者：Biniaz Ahmad; Maheshwari Anil; Smid Michiel^*

来源：Computational Geometry-Theory and Applications, 2014, 47(3): 377-380.

DOI：10.1016/j.comgeo.2013.10.001

• Minimum spanning tree
• Steiner tree
• Bottleneck length
• Yao graph

Let P and S be two disjoint sets of n and m points in the plane, respectively. We consider the problem of computing a Steiner tree whose Steiner vertices belong to S, in which each point of P is a leaf, and whose longest edge length is minimum. We present an algorithm that computes such a tree in O ((n + m) logm) time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model.

• 出版日期2014-4