| Autor: |
Wada, Koichi, Kawaguchi, Kimio, Fujishima, Hideyuki |
| Předmět: |
|
| Zdroj: |
Systems & Computers in Japan; Oct89, Vol. 20 Issue 10, p39-52, 14p |
| Abstrakt: |
In designing VLSI, the problem of bow large the chip area will be is of considers able interest. Thus, the primary objective in investigating this problem is to consider formally processing elements and wires of a circuit to be vertices and edges of an undirected graph, and then clarify the area sufficient or necessary to embed this graph onto a rectangular grid graph according to a certain enbedding method (this is called an embedding model). In this paper, vertices correspond to a rectangular graph such that [length of long side]/[length of short side] ≤ constant, It is shown that under an embedding model, which forbids images of edges (wires) from passing through the inside of the vertex region of the rectangle, the maximum lower bound of the area corresponding to a general n-vertex d-degree graph is Χ(d²n²). As the result, it is seen that the conventionally known upper bound O(d²n²) cannot be improved any further as long as all n-vertex d-degree graphs are considered. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
Plný text