About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
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