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.

Indra Rajasingh

Mathematics

School of Advanced Sciences

Chennai Campus

Rajan R.S

Manuel P.

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

A Linear Time Algorithm for Embedding Christmas Trees into Certain Trees

Parallel Processing Letters

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

In this paper we solve two conjectures proposed by Manuel et al. (2011) [7] to obtain exact wirelength of embedding an r-dimensional hypercube into cylinder C2r1×P2r2 and torus C2r1×C2r2, where r1+r2=r and r1≤r2. We provide a linear time algorithm to compute the exact wirelength of embedding hypercube into cylinder and torus. Further we extend the result for higher dimensional cylinder and torus. © 2014 Elsevier B.V.

Fulltext

Theoretical Computer Science

A linear time algorithm for embedding hypercube into cylinder and torus

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	Parallel Processing Letters
Publisher	World Scientific Pub Co Pte Lt
ISSN	0129-6264
Open Access	0