Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26108
Titel: Routing through a rectangle
Verfasser: Mehlhorn, Kurt
Preparata, Franco P.
Sprache: Englisch
Erscheinungsjahr: 1983
Quelle: Saarbrücken, 1983
Freie Schlagwörter: VLSI
routing
layout
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: In this paper we present an O(Nlog N) algorithm for routing through a rectangle. Consider an n by m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in time O(NlogN) which contrasts favorably to the area of the layout which might be as large as N^{2}. The layout constructed can be wired using 4 layers of interconnect with only O(N) contact-cuts. A partial extension to multi-terminal nets is also discussed.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-41425
hdl:20.500.11880/26164
http://dx.doi.org/10.22028/D291-26108
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Band: 1983/12
SciDok-Publikation: 2-Sep-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1983_12.pdf6,1 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.