Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Zeitschriftenartikel

A faster compaction algorithm with automatic jog insertion

MPG-Autoren
/persons/resource/persons45021

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

/persons/resource/persons45100

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-AE5D-3
Zusammenfassung
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