Three-layer bubble-sorting-based nonManhattan channel routing
Jin-Tai Yan · ACM Transactions on Design Automation of Electronic Systems · 2000
It is well known that a nonManhattan channel router can use fewer routing tracks, and is never worse than a Manhattan router in a channel. To my knowledge, a three-layer bubble-sorting-based nonManhattan channel routing problem is always solved by the solution in a two-layer bubble-sorintg-based nonManhattan channel routing problem. Recently, an O ( kn 2 ) heuristic algorithm [Chaudhary et al. 1991] and an O ( kn 2 ) optimal algorithm [Chen et al. 1994] have been proposed, where k is the number of two-layer routing tracks and n is the number of terminals in a bubble-sorintg-based nonManhattan channel. In this paper we propose an optimal three-layer bubble-sorintg-based nonManhattan routing algorithm to minimize the number of three-layer routing tracks. Furthermore, the time complexity of theis optimal algorithm is proven to be in O ( hn ) time, where h is the number of three-layer routing tracks and n is the number of terminals in a bubble-sorting-based nonManhattan channel.