TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Optimal Routing Through Dense Channels
Citation key Report-318-1992
Author Dorothea Wagner
Pages 269-289
Year 1992
Journal International Journal of Computational Geometry & Applications, 1993
Volume 3
Number 318
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe