An optimal solution to a wire-routing problem (preliminary version)

Martin Tompa

1980 · 17 citations · 4 references

DOIFull text

Open access

Concepts

Abstract

A wire-routing problem which arises commonly in the layout of circuits for very large scale integration (VLSI) is discussed. Given the coordinates of terminals u1, u2, ..., un of one component and v1, v2, ..., vn of another, the problem is to lay out n wires so that the ith wire connects ui to vi, and adjacent wires are separated at least by some fixed distance. The solution with minimum wire length is characterized, and an optimal algorithm which constructs it is presented.

References

4