Name
Abstract | ||
|---|---|---|
Previous literature on very large scale integration routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each “terminal” consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multiport terminals, which gives rise to the group Steiner minimal tree problem. Our main result is the first known approximation algorithm for the group Steiner problem with a sublinear performance bound. In particular, for a net with k multiport terminals, previous heuristics have a performance bound of (k-1)·OPT, while our construction offers an improved performance bound of 2·(2+1n(k/2))·√k·OPT. Our Java implementation is available on the Web |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/43.875285 | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Keywords | DocType | Volume |
VLSI,circuit layout CAD,circuit optimisation,integrated circuit layout,multiport networks,network routing,trees (mathematics),wiring,Java implementation,approximation algorithms,electrically equivalent ports,group Steiner minimal tree problem,minimum-cost routing tree construction,multiport terminals,sublinear performance bound,very large scale integration,wiring estimation | Journal | 19 |
Issue | ISSN | Citations |
10 | 0278-0070 | 2 |
PageRank | References | Authors |
0.42 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. S. Helvig | 1 | 27 | 4.12 |
| G. Robins | 2 | 185 | 28.16 |
| A. Zelikovsky | 3 | 289 | 38.30 |