DocumentCode :
928255
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
Volume :
41
Issue :
3
fYear :
1992
fDate :
3/1/1992 12:00:00 AM
Firstpage :
370
Lastpage :
374
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;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.127452
Filename :
127452
Link To Document :
بازگشت