An optimal solution to a wire-routing problem

摘要

A wire-routing problem which arises commonly in the layout of circuits for very large scale integration is discussed. Given the coordinates of terminals u1, u2,…, un of one component and ν1, α2, …, νn of another, the problem is to lay out n wires so that the ith wire connects νi to νi, 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.