Name
Abstract | ||
|---|---|---|
A fast approach to the minimum rectilinear Steiner tree (MRST) problem is presented. The method yields results that reduce wire length by up to 2% to 3% over the previous methods, and is the first heuristic which has been shown to have a performance ratio less than 3/2; in fact, the performance ratio is less than or equal to 4/3 on the entire class of instances where the ratio c(MST)/c(MRST) is exactly equal to 3/2. The algorithm has practical asymptotic complexity owing to an elegant implementation which uses methods from computation geometry and which parallelizes readily. A randomized variation of the algorithm, along with a batched variant, has also proved successful |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1109/43.144853 | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Keywords | DocType | Volume |
VLSI,circuit layout CAD,graph theory,IC layout,asymptotic complexity,batched variant,computation geometry,implementation,iterative Steiner tree heuristics,minimum rectilinear Steiner tree,parallelizes readily,performance ratio,randomized variation | Journal | 11 |
Issue | ISSN | Citations |
7 | 0278-0070 | 65 |
PageRank | References | Authors |
8.71 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew B. Kahng | 1 | 7582 | 859.06 |
| G. Robins | 2 | 185 | 28.16 |