Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
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
Charles Chiang, Majid Sarrafzadeh, et al.
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
A.C. McKellar, C.K. Wong
Acta Informatica
Majid Sarrafzadeh, C.K. Wong
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
D.T. Lee, C.D. Yang, et al.
Discrete Applied Mathematics