TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel


zur Navigation

Preprints 1993

Optimal Routing Through Dense Channels
Zitatschlüssel Report-318-1992
Autor Dorothea Wagner
Seiten 269-289
Jahr 1992
Journal International Journal of Computational Geometry & Applications, 1993
Jahrgang 3
Nummer 318
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We present a new channel routing algorithm in the knock-knee mode that produces for dense problems area-optimal layouts with minimum total wire length and $\cal O(n)$ bends ($n$ number of nets), where the total number of bends is at most $d-2$ ($d$ density) more than the minimum. The running time is $\cal O(n)$. It thus improves the best previously known algorithm, which determines area-optimal layouts with minimum total wire length in $\cal O(n^2)$ time, where the number of bends is $Ømega(n^2)$. Moreover, the algorithm can be modified so as to guarantee three-layer wirable layouts, where the total wire length is at most $n-2$ more than the minimum. The approach we use is completely different from all previously known algorithms. It is based on the notion of cycle graphs introduced in this paper.
Typ der Publikation Preprint
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe