de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

A faster compaction algorithm with automatic jog insertion

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45100

Näher,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., & Näher, S. (1990). A faster compaction algorithm with automatic jog insertion. IEEE Transactions on CAD of Integrated Circuits and Systems, 9, 158-166.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AE5D-3
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