BOTTLENECK STEINER TREES IN THE PLANE

A Steiner tree with maximum-weight edge minimized is called a bottlene ck Steiner tree (BST). We propose a THETA(\rho\log\rho\) time algorith m for constructing a BST on a point set-rho, with points labeled as St einer or demand; a lower bound, in the linear decision tree model, is also established. We show that if we further want to minimize the numb er of used Steiner points, then the problem becomes NP-complete. Final ly, we show that when locations of Steiner points are not fixed then t he problem remains NP-complete; however, if the topology of the final tree is given, then the problem can be solved in THETA(\rho\log\rho\) time. The BST problem finds application, for example, in VLSI layout, communication network design, and (facility) location problems.