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.

Indra Rajasingh

Mathematics

School of Advanced Sciences

Chennai Campus

Rajan Chattamvalli

Department of Mathematics

Vellore Campus

Sundara Rajan R.

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

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

International Journal of Computer Mathematics

Graph embedding is an important technique that maps a logical graph into a host graph, usually an interconnection network. In this paper, we compute the exact wirelength of embedding Christmas trees into trees. Moreover, we present an algorithm for embedding Christmas trees into caterpillars with dilation 3 proving that the lower bound obtained in [30] is sharp. Further, we solve the maximum subgraph problem for Christmas trees and provide a linear time algorithm to compute the exact wirelength of embedding Christmas trees into trees.

Parallel Processing Letters

A Linear Time Algorithm for Embedding Christmas Trees into Certain Trees

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.

Fulltext

Journal of Discrete Algorithms

Bothway embedding of circulant network into grid

Mathematics in Computer Science

Embedding of Recursive Circulants into Certain Necklace Graphs

The minimum linear arrangement problem is a combinatorial optimization problem whose goal is to find a linear layout of a network in such way that a certain objective cost function is optimized. In this paper, we compute the minimum linear arrangement of incomplete hypercubes using graph embeddings. © 2014 The British Computer Society. All rights reserved.

The Computer Journal

Minimum Linear Arrangement of Incomplete Hypercubes

The dilation of an embedding is defined as the maximum distance between pairs of vertices of host graph that are images of adjacent vertices of guest graph. An embedding with a long dilation faces many problems, such as long communication delay, coupling problems and the existence of different types of uncontrolled noise. In this paper, we compute the minimum dilation of embedding circulant networks into butterfly and benes networks. © Springer International Publishing Switzerland 2015.

Journal	International Journal of Computer Mathematics
Publisher	Informa UK Limited
ISSN	0020-7160
Open Access	0