Provably good moat routing

Moat routing is the routing of nets between the input/output pads and the c ore circuit. In this paper, it is proved that moat routing is NP-complete u nder the routing model in which there are no vertical conflicts and doglegs are disallowed (i.e., every net is routed within a single track). This con trasts with the fact that channel routing is efficiently solvable under the se restrictions. The paper then presents an approximation algorithm for moa t routing that computes moat routing solutions that are guaranteed to use a t most three times the optimal number of tracks. Empirical results are pres ented indicating that for a number of industrial benchmarks, the algorithm produces solutions that are near optimal and that use significantly fewer t racks than previous moat routing strategies. (C) 1999 Published by Elsevier Science B.V. All rights reserved.