On exact solutions to the Euclidean bottleneck Steiner tree problem

Abstract

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio root 2 and there was no known exact algorithm even for k = 1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal Theta(n log n)-time exact algorithm for k = 1 and an O(n(2))-time algorithm for k = 2. Also, we present an optimal Theta(n log n)-time exact algorithm for any constant k for a special case where there is no edge between Steiner points. (C) 2010 Elsevier B.V. All rights reserved.