| Autor: |
Kajitani, Yoji, Tsuji, Katsufumi, Chen, Ray R. |
| Předmět: |
|
| Zdroj: |
Electronics & Communications in Japan, Part 1: Communications; Oct87, Vol. 70 Issue 10, p22-30, 9p |
| Abstrakt: |
Assume a situation in which a block is required to change its relative position at the step where placement and routing in the VLSI layout design has been completed. We formulate a problem of minimizing the number of steps for modification, assuming that we need a step of one unit for rerouting one channel. Then we obtain a solution. For routing, we assume a channel routing style performed channel by channel on the grid determined by a design rule, and that a block movement is required by such slight increase of the width that a new wiring requirement is generated between blocks. The problem is reduced to that of finding an A-confluent cut with total minimum weights for an arbitrarily specified edge set A in a directed graph with weighted edges. By an A-confluent cut with total minimum weights for an arbitrarily specified edge set A in a directed graph with weighted edges. By an A-confluent cut we mean a cut such that the orientation of each constituent edge is the same with respect to edges in A. Although it is a fundamental notion in graph theory. It appears to have been given little consideration. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
