Technical Report 247-1990

Title

Routing through a Dense Channel with Minimum Total Wire Length

Authors

Michael Formann, Dorothea Wagner, and Frank Wagner

Publication

Journal of Algorithms, vol. 15, 1993, pp. 267-283

extended abstract in Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (SODA'91) (1991), pp. 475-482).

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

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 itemize} item routes every solvable channel routing problem item uses minimum area item runs in time linear in the size of the routing area itemize} and itemize} item produces a layout with minimum total wire length itemize} if the channel is dense, i.e. all upper and lower boundary points are occupied by starting or ending wires.