Title :
Bottleneck Steiner trees in the plane
Author :
Sarrafzadeh, M. ; Wong, C.K.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL, USA
fDate :
3/1/1992 12:00:00 AM
Abstract :
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
Keywords :
computational complexity; optimisation; trees (mathematics); NP-complete; VLSI layout; bottleneck Steiner trees; communication network design; linear decision tree model; location problems; lower bound; maximum-weight edge minimized; Algorithm design and analysis; Binary search trees; Communication networks; Decision trees; Geometry; Joining processes; Network topology; Steiner trees; Tree graphs; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on