direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1990

Routing through a Dense Channel with Minimum Total Wire Length
Zitatschlüssel Report-247-1990
Autor Michael Formann and Dorothea Wagner and Frank Wagner
Seiten 267-283
Jahr 1990
Journal Journal of Algorithms, 1993
Jahrgang 15
Nummer 247
Notiz extended abstract in Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (SODA'91) (1991)\/, pp. 475-482).
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We present a new efficient channel routing algorithm in the knock-knee mode. Most investigations in the past were concerned only with the solution of the layout problem but especially if no or only few boundary points are free, the resulting layout contains a lot of wires making unnecessarily long detours. Our algorithm \beginitemize \item routes every solvable channel routing problem \item uses minimum area \item runs in time linear in the size of the routing area \enditemize and \beginitemize \item produces a layout with minimum total wire length \enditemize if the channel is dense, i.e. all upper and lower boundary points are occupied by starting or ending wires.
Typ der Publikation Preprint
Download Bibtex Eintrag