A fast algorithm for optimal via-shifting in channel compaction

The authors consider the problem of shifting vias to obtain more compactable channel routing solutions. Given a grid-based two-layer channel routing solution S, one can obtain a new routing solution S' by simply shifting the vias in S. In this case, S' is said to be derivable from S. The authors address the problem of how to obtain a routing solution S' from S by shifting vias so that S' would achieve minimum channel height after compaction. They present some necessary preliminary material and give the boolean procedure which forms the backbone of the algorithm. They present the optimal algorithm for shifting for the channel routing solution. The worst-case time complexity of the algorithm is considered. The algorithm uses a technique which is similar to the greedy algorithm for computing a maximum matching for a special class of bipartite graphs called convex bipartite graphs.