Please use this identifier to cite or link to this item:
https://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 | 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 | 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.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.