TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1990

COGA 5-Wheel

Page Content

to Navigation

Preprints 1990

Routing through a Dense Channel with Minimum Total Wire Length
Citation key Report-247-1990
Author Michael Formann and Dorothea Wagner and Frank Wagner
Pages 267-283
Year 1990
Journal Journal of Algorithms, 1993
Volume 15
Number 247
Note 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
Abstract 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.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe