New approximation algorithms for routing with multiport terminals

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)) . rootk . OPT. Our Java implementation is available on the Web.