Name
Title | ||
|---|---|---|
An O(nlogn) edge-based algorithm for obstacle-avoiding rectilinear steiner tree construction |
Abstract | ||
|---|---|---|
Obstacle-avoiding Steiner tree construction is a fundamental problem in VLSI physical design. In this paper, we provide a new approach for rectilinear Steiner tree construction in the presence of obstacles. We propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. We design a fast algorithm for the minimum terminal spanning tree construction, which is the bottleneck step of several existing approaches in terms of running time. We adopt an edge-based heuristic, which enables us to perform both local and global refinement, leading to Steiner trees with small lengths. The time complexity of our algorithm is O(nlogn). Hence, our technique is the most efficient one to the best of our knowledge. Experimental results on various benchmarks show that our algorithm achieves 25.8 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 1.58% larger than the best existing solution |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1353629.1353658 | ISPD |
Keywords | DocType | Citations |
average length,Steiner tree,VLSI physical design,rectilinear Steiner tree construction,obstacle-avoiding rectilinear Steiner tree,edge-based algorithm,rectilinear steiner tree construction,existing approach,fast algorithm,novel algorithm,tree construction,Obstacle-avoiding Steiner tree construction | Conference | 5 |
PageRank | References | Authors |
0.49 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jieyi Long | 1 | 129 | 8.98 |
| Hai Zhou | 2 | 85 | 6.30 |
| Seda Öǧrenci Memik | 3 | 488 | 42.57 |