Optimal path embedding in crossed cubes

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

88 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1190-1200
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume16
Issue number12
Publication statusPublished - Dec 2005

Abstract

The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between [n+1/2] + 1 and 2n - 1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that [n+1/ 2] is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube. © 2005 IEEE.

Research Area(s)

  • Crossed cube, Graph embedding, Interconnection network, Optimal embedding, Parallel computing system

Citation Format(s)

Optimal path embedding in crossed cubes. / Fan, Jianxi; Lin, Xiaola; Jia, Xiaohua.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 16, No. 12, 12.2005, p. 1190-1200.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review