| New Approximation Algorithms for Routing with Multi-Port Terminals (2007) | |||||||||||||||||
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. Keywords: Routing, Multi-Port Terminals, Steiner Trees, Group Steiner Problem, Com... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||