An extended 1-D assignment problem: net assignment in gate matrix layout
A formulation for the net assignment problem in gate matrix layout is presented. A problem called the extended one-dimensional assignment problem is defined. A heuristic algorithm for solving this extended one-dimensional assignment problem is proposed. Since the net assignment problem in gate matrix is the extended one-dimensional assignment problem exactly, this algorithm is applied to the net assignment. The time complexity of the algorithm is bounded by O(m*n/sup 2/), where n is the number of nets and m is the sum of the number of vertical diffusion runs and the number of gates.<<ETX>>