Via minimization in VLSI routing with movable terminals

A unified approach is developed for solving the general problem of minimizing the number of via holes in a two-layer very large-scale integration (VLSI) channel and switch-box routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switch-box routing, and (iii) four-sided switch-box routing. The concept of a maximum parallel set of edges in a bipartite graph is introduced to solve the minimization problem. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is O(N log N), in all three cases, where N is the number of pairs of terminals to be connected