Title :
Hierarchical Steiner tree construction in uniform orientations
Author :
Sarrafzadeh, Majid ; Wong, C.K.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL, USA
fDate :
9/1/1992 12:00:00 AM
Abstract :
A hierarchical approach to Steiner tree construction in λ-geometry is proposed. The algorithm runs in time O(n log n) and the length of the constructed tree is at most [σ/cos(π/2λ)] times (for λ=2, 3/2 times) the length of the optimal Steiner tree where n is the cardinality of the point set and it was recently proved that σ is (2/√3). How to trade off between the running time of the algorithm and the length of the produced Steiner tree is shown. Given enough time, an optimal Steiner tree will be obtained. The algorithm is extended to construct a Steiner tree of a set of subtrees (i.e., partial trees) and runs in O(λN log N) time, where N is the total number of edges of the subtrees
Keywords :
VLSI; network routing; network topology; trees (mathematics); λ-geometry; Steiner tree construction; cardinality; hierarchical approach; partial trees; point set; subtrees; Communication networks; Extraterrestrial measurements; Geometry; Polynomials; Position measurement; Senior members; Steiner trees; Surface-mount technology; Time measurement; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
