Exact Algorithms for the Bottleneck Steiner Tree Problem (Extended Abstract)

Given n terminals in the plane R-2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points in R-2 so that the longest edge length of the resulting Steiner tree is minimized. In this paper, we study this problem in any L metric. We present the first fixed-parameter tractable algorithm running in O(f (k) . n(2) log n) time for the L-1 and the L-infinity metrics, and the first exact algorithm for any other L-p metric with 1 < p < infinity whose time complexity is O(f (k) . (n(k) + n log n)), where f (k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L-2 metric, and our algorithms take a polynomial time in n for fixed k.