Bottleneck Steiner Trees in the Plane

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