An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints

A popular algorithm to compact a VLSI symbolic layout is to use a graph algorithm similar to finding the 'longest-path' in a network. The algorithm assumes that the spacing constraints on the mask elements are of the lower-bound type. However, to enable the user to have close control over the compaction result, a desired symbolic layout system should allow the user to add either the equality or the upper-bound constraints on selected pairs of mask elements as well. This paper proposes an algorithm which uses a graph-theoretic approach to solve efficiently the compaction problem with mixed constraints.