Bottleneck Steiner trees in the plane

A Steiner tree with maximum-weight edge minimized is called a bottleneck Steiner tree (BST). The authors propose a Θ(|ρ| log |ρ|) time algorithm for constructing a BST on a point set ρ, with points labeled as Steiner or demand; a lower bound, in the linear decision tree model, is also established. It is shown that if it is desired to minimize further the number of used Steiner points, then the problem becomes NP-complete. It is shown that when locations of Steiner points are not fixed the problem remains NP-complete; however, if the topology of the final tree is given, then the problem can be solved in Θ(|ρ| log |ρ|) time. The BST problem can be used, for example, in VLSI layout, communication network design, and (facility) location problems