AN EFFICIENT ALGORITHM FOR THE SPLIT K-LAYER CIRCULAR TOPOLOGICAL VIAMINIMIZATION PROBLEM

The split k-layer (k greater than or equal to 2) circular topological via minimization (k-CTVM) problem is reconsidered here. The problem is finding a topological routing of the n nets, using k available layers , such that the total number of vias is minimized. The optimal solutio n of this problem is solved in O(n(2k+l)) time. However, such an algor ithm is inefficient even for n greater than or equal to 8 and k greate r than or equal to 2. A heuristic algorithm with complexity of O(k n(4 )) is presented. When the experimental results of this algorithm and t hat of an exhaustive algorithm are compared, the same number of optima l solutions is obtained from this heuristic algorithm for all permutat ions of 1) n = 8 with k = 2 or 3, and 2) n = 10 with k = 3. For other cases, the number of optimal solutions from this algorithm depends on the permutations been selected; and this number, in general, will incr ease as k increases.