Please use this identifier to cite or link to this item:
Title: Fast vicinity-upgrade algorithm for rectilinear Steiner trees
Authors: Chua, J.K.
Lim, Y.C. 
Issue Date: 1-Jan-1991
Citation: Chua, J.K.,Lim, Y.C. (1991-01-01). Fast vicinity-upgrade algorithm for rectilinear Steiner trees. Electronics Letters 27 (13) : 1139-1141. ScholarBank@NUS Repository.
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.
Source Title: Electronics Letters
ISSN: 00135194
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Sep 22, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.