TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1990

COGA 5-Wheel

Page Content

to Navigation

Preprints 1990

Channel Routing under Different Optimization Criteria
Citation key Report-240-1989
Author Dorothea Wagner and Frank Wagner
Pages 295-305
Year 1989
Journal Methods of Operations Research, 1990
Volume 62
Number 240
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Channel routing is a basic problem in the design of VLSI-circuits and has received considerable attention in the past. There are essentially two different routing models: Knock-knee routing and Manhattan routing. We consider the knock-knee model; only two terminal nets are involved. The channel routing problem (CRP) is given by a bounded rectangle in a rectilinear grid (the channel) and a collection of pairs of terminals (called nets), where the input terminal lies on the upper boundary and the exit terminal lies on the lower boundary of the channel. The layout consists of edge-disjoint paths (called wires) through the channel connecting the input- and the exit terminal of the nets. To avoid physical contacts between the wires, the edges of the paths are assigned to different layers, such that no two wires share a grid point in the same layer (called wiring). Connections between distinct layers (called vias) are placed on grid points. For the design of algorithms solving the layout respectively wiring problem the following criteria are of central importance: The area of the layout, the length of the wires, the number of layers, the \it number of vias and the complexity of the algorithm. In this paper we present two new algorithms, that guarantee good respectively optimal solutions for these problems.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe