Embedding of Complete graphs and Cycles into Grids with holes

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, s...

Full description

Saved in:
Bibliographic Details
Published in:Procedia computer science 2020, Vol.172, p.115-121
Main Authors: Mary, R. Stalin, Rajasingh, Indra
Format: Article
Language:English
Subjects:
Congestion Lemma
Embedding
Transmission
Wiener Index
Wirelength
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1877-0509
1877-0509
DOI:10.1016/j.procs.2020.05.017