Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We present an algorithm to find a set of all optimal solutions for a channel

replacement problem. A channel consists of two rows of horizontal line

segments (representing components). Each line segment contains some terminals

with fixed positions. Sets of terminals, callednets, are to be

connected. The relative ordering of line segments in each row is fixed. The

line segments can be shifted left or right, which will affect the width needed

for routing and the length of the channel. We want to find the tradeoff

between channel length and routing width. Since the channel routing problem

is NP--complete, we use a lower bound on routing width, called density. Thedensityof a placement is the maximum number of nets crossing each

vertical cut. We can increase the total length to minimize the channel

density, or minimize the total length by increasing the channel density. The

pair (density, total length) is called theshapeof a placement.

A shape is minimal if a decrease in density would cause an increase in

total length, and vice versa. Our algorithm computes all the minimal

shapes inO(N4) time, whereNis the number of nets. This is the

first known polynomial algorithm for this problem.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/281

[2] http://www.cs.princeton.edu/research/techreps/author/380

[3] ftp://ftp.cs.princeton.edu/techreports/1992/384.ps.gz