ON VLSI LAYOUT COMPACTION WITH MIXED GRID AND EDGE CONSTRAINTS.

The modeling and solution techniques of VLSI-layout compaction are investigated using the constraint graph approach under various practical design considerations. In particular, the graph method is extended to the compaction of VLSI layout with mixed grid constraints in addition to the usual minimum and maximum type constraints. This is a mixed integer problem. It is shown that it can be solved by the search of effectively longest paths, and a fast algorithm is presented.