DocumentCode
1080542
Title
Fast vicinity-upgrade algorithm for rectilinear Steiner trees
Author
Chua, J.K. ; Lim, Yang Choon
Author_Institution
Dept. of Electr. Eng., Nat. Univ. of Singapore, Singapore
Volume
27
Issue
13
fYear
1991
fDate
6/20/1991 12:00:00 AM
Firstpage
1139
Lastpage
1141
Abstract
A new algorithm for rectilinear Steiner trees (RST) is presented. The proposed algorithm is based on successively constructing a vicinity structure from a rectilinear minimum spanning tree (MST) and generating a refined RST. The algorithm achieves an 8.5-10% average cost improvement over the rectilinear MST at a time complexity of O(n log n). To address specifically the linear programming approach of global routing the algorithm is modified to generate K trees.
Keywords
VLSI; circuit layout CAD; computational complexity; linear programming; network topology; trees (mathematics); C language implementation; CAD; VLSI design; fast vicinity upgrade algorithm; global routing; linear programming; rectilinear Steiner trees; rectilinear minimum spanning tree; time complexity;
fLanguage
English
Journal_Title
Electronics Letters
Publisher
iet
ISSN
0013-5194
Type
jour
DOI
10.1049/el:19910710
Filename
132712
Link To Document