Minimizing external wires in generalized single-row routing

Much of the recent work on the automated design of VLSI chips has concentrated on routing problems associated with such designs. One major class of routing problems focuses on single-row routing. Recently, the traditional single-row routing model has been generalized to allow external wires. Under this generalized model, it is possible to route many more single-row routing instances than in the traditional model. There is, however, a clear disadvantage in the use of external wires, since they force a lengthening of the channels surrounding the single row of terminals. Thus, it is desirable for these generalized single-row routings to use a minimum number of external wires. A linear-time algorithm for determining the minimum number of external wires needed to route a given instance of single-row routing is provided here