## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 1940-1943 |

Number of pages | 4 |

Journal | Proceedings - IEEE International Symposium on Circuits and Systems |

Volume | 4 |

State | Published - Dec 1 1991 |

Externally published | Yes |

Event | 1991 IEEE International Symposium on Circuits and Systems Part 4 (of 5) - Singapore, Singapore Duration: Jun 11 1991 → Jun 14 1991 |

## ASJC Scopus subject areas

- Electrical and Electronic Engineering