Loading...
Please wait, while we are loading the content...
Similar Documents
New approximation algorithms for routing with multi-port terminals.
| Content Provider | CiteSeerX |
|---|---|
| Author | Helvig, C. S. Robins, Gabriel Zelikovsky, Alexander |
| Abstract | Previous literature on VLSI 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 multi-port 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 sub-linear performance bound. In particular, for a net with k multi-port terminals, previous heuristics have a performance bound of (k \Gamma 1) \Delta OPT , while our construction offers an improved performance bound of 2 \Delta (2 + ln k 2 ) \Delta p k \Delta OPT . Our Java implementation is available on the Web. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Multi-port Terminal New Approximation Algorithm Delta Opt Minimum-cost Routing Tree Construction Sub-linear Performance Bound Large Collection Group Steiner Problem Approximation Algorithm Group Steiner Performance Bound Previous Literature Main Result One-to-one Correspondence Java Implementation Equivalent Port Improved Performance Bound Tree Problem General Problem Layout Step Previous Heuristic |
| Content Type | Text |
