Optimal via-shifting in channel compaction

The authors study the problem of shifting vias to obtain more compactable two-layer channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v_c be the number of grid points on column c that are occupied by vias. Let w_c be the number of grid points on column c that are occupied by horizontal wires. They define the height of a column c to be the quantity h _c=Av_c+Bw_c+C , where A, B, C are some design rule dependent constants. A column is said to be critical if it is a column with maximum height. Let H_S be the height of the critical column(s) in S. In general, H_S is a good measure of the channel height after compaction. They show that the problem of shifting vias to minimize H_S can be solved optimally in polynomial time. The complexity of the optimal via-shifting algorithm is O(WL(V+L)log²(V+ L)) where W, L, and V are the number of tracks in S, the number of columns in S, and the number of vias in S, respectively