Partioning problem of optimal layout for integrated circuits

The paper consists of four parts. In the first part the integrated circuits layout problem is considered from a very general viewpoint. In the second part the partitioning problem is defined and its role in the general layout process analysed: applications to particular circuit classes are indicated, together with a classification of algorithmic approaches to the problem. The third part gives a rigorous formulation of the partitioning problem, which is shown to reply a relevant number of major Combinatorial Optimization Problems as a particular case. Finally, in the fourth part a heuristic procedure to the solution of circuit bipartition problems is presented.