Name
Title | ||
|---|---|---|
An O(n log n) path-based obstacle-avoiding algorithm for rectilinear Steiner tree construction |
Abstract | ||
|---|---|---|
For the obstacle-avoiding rectilinear Steiner minimal tree problem, this paper presents an O(n log n)-time algorithm with theoretical optimality guarantees on a number of specific cases, which required O(n3) time in previous works. We propose a new framework to directly generate O(n) critical paths as essential solution components, and prove that those paths guarantee the existence of desirable solutions. The path-based framework neither generates invalid initial solutions nor constructs connected routing graphs, and thus provides a new way to deal with the OARSMT problem. Experimental results show that our algorithm achieves the best speed performance, while the average wirelength of the resulting solutions is only 1.1% longer than that of the best existing solutions. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1629911.1629998 | DAC |
Keywords | Field | DocType |
rectilinear steiner tree construction,average wirelength,essential solution component,path-based framework,best speed performance,new framework,critical path,n log n,time algorithm,path-based obstacle-avoiding algorithm,oarsmt problem,desirable solution,routing,algorithm design and analysis,physical design,steiner trees,computational complexity,construction industry,geometry,steiner tree,spanning tree,data mining,tree graphs,obstacle avoidance | Discrete mathematics,Combinatorics,Tree (graph theory),Algorithm design,Steiner tree problem,Computer science,Algorithm,Rectilinear Steiner tree,Spanning tree,Physical design,Time complexity,Computational complexity theory | Conference |
ISSN | Citations | PageRank |
0738-100X | 11 | 0.73 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chih-Hung Liu | 1 | 50 | 4.82 |
| Shih-Yi Yuan | 2 | 53 | 7.48 |
| Sy-Yen Kuo | 3 | 2304 | 245.46 |
| Yao-Hsin Chou | 4 | 151 | 24.63 |