hide
Free keywords:
-
Abstract:
The work of F.M. Maley (Proc. Chapel Hill Conf. on VLSI, p.261-83, 1985) on
one-dimensional compaction with automatic jog insertion is refined. More
precisely, an algorithm with running time O((n2+k)log n), where k=O(n3) is a
quantity which measures the difference between the input and output sketch, is
given, and Maley's O(n4) algorithm is improved. The compaction algorithm takes
as input a layout sketch, the wires in a layout sketch are flexible and only
indicate the topology of the layout. The compactor minimizes the horizontal
width of the layout while maintaining its routability. The exact geometry of
the wires is filled in by a router after compaction
