Fast vicinity-upgrade algorithm for rectilinear Steiner trees |
| |
| Authors: | Chua JK Lim YC |
| |
| Affiliation: | Dept. of Electr. Eng., Nat. Univ. of Singapore, Singapore; |
| |
| 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: | |
|
|
