Double‐row planar routing and permutation layout

Publisher Website
Google Scholar
Abstract
Problems on layout for ICs (integrated circuits) and PCBs (printed circuit boards) are usually solved by heuristic approaches because they are complex. This article considers a special problem of double‐row planar routing. The problem represents a generalization of the permutation layout problem to which estimation of bounds and some algorithms have been proposed recently. Our approach is based on the interval graphical representation introduced in the single‐row single‐layer PCB problem. The objective function for minimization is the breadth of the realization, i.e., the total number of vertical tracks required to realize a given net list specified in terms of terminals on two parallel rows. The problem is shown to be intractable in the sense of NP‐completeness; however, a polynomial‐time heuristic algorithm is proposed. An upper bound for the breadth for an initial solution is given. Iterative improvement is next used. The algorithm has been programmed in FORTRAN and ran on the VAX 11/780 computer.

This publication has 6 references indexed in Scilit: