Graph embedding is an important technique that maps a guest graph into a host graph, usually an interconnection network. In this paper, we compute the dilation and wirelength of embedding circulant network into grid and vice versa. © 2015 Elsevier B.V.

Indra Rajasingh

Mathematics

School of Advanced Sciences

Chennai Campus

Sundara Rajan C-R

Department of General Management

VIT Business School

Vellore Campus

Parthiban N

Rajalaxmi T.M.

Fulltext

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Journal of Discrete Algorithms

Hypercubes are a very popular model for parallel computation because of their regularity and the relatively small number of interprocessor connections. In this paper, we present an algorithm for embedding special class of circulant networks into their optimal hypercubes with dilation 2 and prove its correctness. Also, we embed special class of circulant networks into special class of generalized Petersen graphs with dilation 2 and vice versa. © 2012 Taylor &amp; Francis.

International Journal of Computer Mathematics

Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs

Graph embedding has been known as a powerful tool for implementation of parallel algorithms and simulation of interconnection networks. In this paper, we introduce a technique to obtain a lower bound for the dilation of an embedding. Moreover, we give algorithms for embedding variants of hypercubes with dilation 2 proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding folded hypercubes and augmented cubes into hypercubes.

Journal of Interconnection Networks

EMBEDDING VARIANTS OF HYPERCUBES WITH DILATION 2

Journal of Combinatorial Optimization

Embeddings of circulant networks

Information Processing Letters

Embedding of hypercubes into necklace, windmill and snake graphs

Discrete Applied Mathematics

Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength

Bothway embedding of circulant network into grid

Journal	Data powered by TypesetJournal of Discrete Algorithms
Publisher	Data powered by TypesetElsevier BV
ISSN	1570-8667
Open Access	Yes