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.

Sundara Rajan C-R

Department of General Management

VIT Business School

Vellore Campus

Indra Rajasingh

Mathematics

School of Advanced Sciences

Chennai Campus

Miller, Mirka

Miller M

Parthiban N

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

The Computer Journal

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

An incomplete recursive circulant possesses virtually every advantage of a complete recursive circulant, including simple deadlock-free routing, a small diameter, a good support of parallel algorithms, and so on. It is natural to reconfigure a faulty recursive circulant into a maximum incomplete recursive circulant so as to lower potential performance degradation. For [Formula: see text], the maximum incomplete subgraph problem is to identify a subgraph [Formula: see text] of a graph [Formula: see text] on [Formula: see text] vertices having the maximum number of edges among all subgraphs on [Formula: see text] vertices and is NP-complete. In this paper we identify maximum incomplete recursive circulants and use them as a tool to compute the exact wirelength of embedding recursive circulants into special classes of trees, such as [Formula: see text]-rooted complete binary trees, [Formula: see text]-rooted sibling trees, binomial trees, certain caterpillars and path.

Discrete Mathematics, Algorithms and Applications

Maximum incomplete recursive circulants in graph embeddings

A Lower Bound for Dilation of an Embedding

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	Data powered by TypesetThe Computer Journal
Publisher	Data powered by TypesetOxford University Press (OUP)
ISSN	0010-4620
Open Access	0