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

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

• 1: M. R. Garey , R. L. Graham , D. S. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.10-22, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803626]
• 2: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 3: Mead, C.A. VLSI Design Course. Offered at University of Washington, August 20 - September 14, 1979.
• 4: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 5: Reif, J.H. Complexity of the Mover's Problem and Generalizations. 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico (October 1979), 421–427.
• 6: Shamos, M.I. and Hoey, D. Geometric Intersection Problems. 17th Annual Symposium on Foundations of Computer Science, Houston, Texas (October 1976), 208–215.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Algorithms, Design, Theory