Method for Finding the Maximum Alignment of Terminals
Original Publication Date: 1985-Mar-01
Included in the Prior Art Database: 2005-Feb-18
This article relates to the problem of finding a maximum subset of a given set of wires connecting two rows of terminals with fixed positions, such that no wires in the subset cross. An algorithm is derived that runs in time O(p + (n p)lg(p + 1)), where n is the number of wires given and p is the maximum number of noncrossing wires; in many practically relevant cases, e.g., when p is very high, it needs only linear time. In VLSI wiring, cascode-switch macro wiring, and the pin permutation problem, the problem of finding a maximum subset of noncrossing wires in a situation as in Fig. 1 is encountered. In the top row, terminals are numbered from 1 to n from left to right; in the bottom row, these numbers are arbitrarily permuted. Each pair of terminals having the same numbers is to be connected by a straight wire.