TY - JOUR
T1 - Optimal path embedding in crossed cubes
AU - Fan, Jianxi
AU - Lin, Xiaola
AU - Jia, Xiaohua
PY - 2005/12
Y1 - 2005/12
N2 - 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.
AB - 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.
KW - Crossed cube
KW - Graph embedding
KW - Interconnection network
KW - Optimal embedding
KW - Parallel computing system
UR - http://www.scopus.com/inward/record.url?scp=30344464391&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-30344464391&origin=recordpage
U2 - 10.1109/TPDS.2005.151
DO - 10.1109/TPDS.2005.151
M3 - 21_Publication in refereed journal
VL - 16
SP - 1190
EP - 1200
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
SN - 1045-9219
IS - 12
ER -