Embedding of Complete graphs and Cycles into Grids with holes
Citations Over Time
Abstract
An important feature of an interconnection network is its ability to efficiently simulate one architecture by another. Such a simulation problem can be mathematically formulated as a graph embedding problem. Although the definition of an embedding is an into mapping from Guest Graph to Host Graph, so far in the literature, the embedding has been considered as a mapping from G onto H. In other words, the number of processors in G and H are considered to be the same. In this paper, we increase the number of processors in H by 1. The question is to find the processor in H which does not have the pre-image under the embedding mapping, so that the wirelength of the embedding is minimum. We relate this problem to finding transmission of vertices in the host graph.