Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/62190
Title: Fast vicinity-upgrade algorithm for rectilinear Steiner trees
Authors: Chua, J.K.
Lim, Y.C. 
Issue Date: 1-Jan-1991
Source: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/62190
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)

20
checked on Dec 15, 2017

Google ScholarTM

Check


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