Topological Via Minimization Problem for Permutation Layout when No Wire Passes between Pins.

This paper considers the topological via minimization problem in the permutation layout, under the constraint that no wire passes between pins which are adjacent on the same horizontal line. Under a constraint that the upper side of the upper horizontal line not be used as the wiring area, an algorithm is proposed with time complexity (n² log n) for k = 1 and O(n3k-1) for the general value of k, for the problem of determining the set of maximum k-layer wiring (n is the number of nets). Then an algorithm is proposed with time complexity O(8kn3k-1) for the case where the wiring can be the whole plane. [ABSTRACT FROM AUTHOR]