loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Optimal Path Embedding in Crossed Cubes
December 2005 (vol. 16 no. 12)
pp. 1190-1200
ASCII Text
x 
 
Jianxi Fan, Xiaola Lin, Xiaohua Jia, "Optimal Path Embedding in Crossed Cubes," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp. 1190-1200, December, 2005.
 
 
BibTex
x
 
@article{ 10.1109/TPDS.2005.151,
author = {Jianxi Fan and Xiaola Lin and Xiaohua Jia},
title = {Optimal Path Embedding in Crossed Cubes},
journal ={IEEE Transactions on Parallel and Distributed Systems},
volume = {16},
number = {12},
issn = {1045-9219},
year = {2005},
pages = {1190-1200},
doi = {http://doi.ieeecomputersociety.org/10.1109/TPDS.2005.151},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Parallel and Distributed Systems
TI - Optimal Path Embedding in Crossed Cubes
IS - 12
SN - 1045-9219
SP1190
EP1200
EPD - 1190-1200
A1 - Jianxi Fan,
A1 - Xiaola Lin,
A1 - Xiaohua Jia,
PY - 2005
KW - Crossed cube
KW - graph embedding
KW - optimal embedding
KW - interconnection network
KW - parallel computing system.
VL - 16
JA - IEEE Transactions on Parallel and Distributed Systems
ER -
 

Abstract—The crossed cube is an important variant of the hypercube. The n{\hbox{-}}{\rm{dimensional}} crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n{\hbox{-}}{\rm{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 \lceil{\frac{n+1}{2}}\rceil +1 and 2^n-1 can be embedded between any two distinct nodes with a dilation of 1 in the n{\hbox{-}}{\rm{dimensional}} crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that \lceil{\frac{n+1}{2}}\rceil+1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n{\hbox{-}}{\rm{dimensional}} crossed cube.

[1] L. Auletta, A.A. Rescigno, and V. Scarano, “Embedding Graphs onto the Supercube,” IEEE Trans. Computers, vol. 44, no. 4, pp. 593-597, Apr. 1995.[2] M.M. Bae and B. Bose, “Edge Disjoint Hamiltonian Cycles in $k{\hbox{-}}{\rm{Ary}}$ $n{\hbox{-}}{\rm{Cubes}}$ and Hypercubes,” IEEE Trans. Computers, vol. 52, no. 10, pp. 1271-1284, Oct. 2003.[3] S.L. Bezrukov, J.D. Chavez, L.H. Harper et al., “The Congestion of $n{\hbox{-}}{\rm{Cube}}$ Layout on a Rectangular Grid,” Discrete Math., vol. 213, nos. 1-3, pp. 13-19, Feb. 2000.[4] R.V. Boppana, S. Chalasani, and C.S. Raghavendra, “Resource Deadlock and Performance of Wormhole Multicast Routing Algorithms,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 6, pp. 535-549, June 1998.[5] A. Broder, F. Frieze, and E. Upfal, “Existence and Construction of Edge-Disjoint Paths on Expander Graphs,” SIAM J. Computing, vol. 23, pp. 976-989, 1994.[6] M.Y. Chan and S.-J. Lee, “Fault-Tolerant Embedding of Complete Binary Trees in Hypercubes,” IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 3, pp. 277-288, Mar. 1993.[7] C.-P. Chang, T.-Y. Sung, and L.-H. Hsu, “Edge Congestion and Topological Properties of Crossed Cubes,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 1, pp. 64-80, Jan. 2000.[8] V. Chaudhary and J.K. Aggarwal, “Generalized Mapping of Parallel Algorithms onto Parallel Architectures,” Proc. Int'l Conf. Parallel Processing, pp. 137-141, Aug. 1990.[9] K. Efe, “A Variation on the Hypercube with Lower Diameter,” IEEE Trans. Computers, vol. 40, no. 11, pp. 1312-1316, Nov. 1991.[10] K. Efe, “The Crossed Cube Architecture for Parallel Computing,” IEEE Trans. Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, Sept.-Oct. 1992.[11] K. Efe, P.K. Blachwell, W. Slough, and T. Shiau, “Topological Properties of the Crossed Cube Architecture,” Parallel Computing, vol. 20, pp. 1763-1775, 1994.[12] J. Fan, “Diagnosability of Crossed Cubes under the Comparison Diagnosis Model,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 10, pp. 1099-1104, Oct. 2002.[13] J. Fan, “Diagnosability of the Möobius Cubes,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-929, Sept. 1998.[14] J. Fan and X. Lin, “The $t/k{\hbox{-}}{\rm{Diagnosability}}$ of the BC Graphs,” IEEE Trans. Computers, vol. 53, no. 2, pp. 176-184, Feb. 2005.[15] J. Fan, X. Lin, and X. Jia, “Node-Pancyclicity and Edge-Pancyclicity of Crossed Cubes,” Information Processing Letters, vol. 93, pp. 133-138, Feb. 2005.[16] J.-S. Fu, “Fault-Tolerant Cycle Embedding in the Hypercube,” Parallel Computing, vol. 29, no. 6, pp. 821-832, June 2003.[17] Q.-P. Gu and S. Peng, “Optimal Algorithms for Node-to-Node Fault Tolerant Routing in Hypercubes,” Computer J., vol. 39, no. 7, pp. 626-629, July 1996.[18] Q.-P. Gu and S. Peng, “Unicast in Hypercubes with Large Number of Faulty Nodes,” IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 10, pp. 964-975, Oct. 1999.[19] S.-Y. Hsieh, G.-H. Chen, and C.-W. Ho, “Longest Fault-Free Paths in Star Graphs with Edge Faults,” IEEE Trans. Computers, vol. 50, no. 9, pp. 960-971, Sept. 2001.[20] S.-Y. Hsieh, G.-H. Chen, and C.-W. Ho, “Longest Fault-Free Paths in Star Graphs with Vertex Faults,” Theoretical Computer Science, vol. 262, nos. 1-2, pp. 215-227, 2001.[21] S.-Y. Hsieh, C.-W. Ho, and G.-H. Chen, “Fault-Free Hamiltonian Cycles in Faulty Arrangement Graphs,” IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 3, pp. 223-237, Mar. 1999.[22] H.-C. Hsu, T.-K. Li, J.J.M. Tan, and L.-H. Hsu, “Fault Hamiltonicity and Fault Hamiltonian Connectivity of the Arrangement Graphs,” IEEE Trans. Computers, vol. 53, no. 1, pp. 39-53, Jan. 2004.[23] W.-T. Huang, Y.-C. Chuang, J.M. Tan, and L.-H. Hsu, “On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes,” IEICE Trans. Fundamentals, vol. E85-A, no. 6, pp. 1359-1370, June 2002.[24] P. Kulasinghe, “Connectivity of the Crossed Cube,” Information Processing Letters, vol. 61, pp. 221-226, July 1997.[25] P. Kulasinghe and S. Bettayeb, “Embedding Binary Trees into Crossed Cubes,” IEEE Trans. Computers, vol. 44, no. 7, pp. 923-929, July 1995.[26] J. Kzeinberg and E. Tardos, “Disjoint Paths in Densely Embedded Graphs,” Proc. 36th Ann. Symp. Foundations of Computer Science, pp. 52-61, Oct. 1995.[27] X. Lin, P.K. Mckinley, and L.M. Ni, “Deadlock-Free Multicast Wormhole Routing in 2D Mesh Multicomputers,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 8, pp. 793-804, Aug. 1994.[28] X. Lin and L.M. Ni, “Deadlock-Free Multicast Wormhole Routing in Multicomputer Networks,” Proc. 18th Ann. Int'l Symp. Computer Architecture, pp. 116-125, 1991.[29] R.-S. Lo and G.-H. Chen, “Embedding Hamiltonian Paths in Faulty Arrangement Graphs with the Backtracking Method,” IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 2, pp. 209-222, Feb. 2001.[30] A. Matsubayashi, “VLSI Layout of Trees into Grids of Minimum Width,” IEICE Trans. Fundamentals, vol. E87-A, no. 5, pp. 1059-1069, May 2004.[31] A. Patel, A. Kusalik, and C. McCrosky, “Area-Efficient VLSI Layouts for Binary Hypercubes,” IEEE Trans. Computers, vol. 49, no. 2, pp. 160-169, Feb. 2000.[32] Y.-C. Tseng, S.-H. Chang, and J.-P. Sheu, “Fault-Tolerant Ring Embedding in a Star Graph with Both Link and Node Failures,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185-1195, Dec. 1997.[33] M.-C. Yang, T.-K. Li, J.J.M. Tan, L.-H. Hsu, “Fault-Tolerant Cycle-Embedding of Crossed Cubes,” Information Processing Letters, vol. 88, no. 4, pp. 149-154, Nov. 2003.[34] P.-J. Yang, S.-B. Tien, and C.S. Raghavendra, “Embedding of Rings and Meshes onto Faulty Hypercubes Using Free Dimensions,” IEEE Trans. Computers, vol. 43, no. 5, pp. 608-613, May 1994.[35] X. Yang and G. Megson, “On the Path-Connectivity, Vertex-Pancyclicity, and Edge-Pancyclicity of Crossed Cubes,” manuscript.

Index Terms:
Crossed cube, graph embedding, optimal embedding, interconnection network, parallel computing system.
Citation:
Jianxi Fan, Xiaola Lin, Xiaohua Jia, "Optimal Path Embedding in Crossed Cubes," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp. 1190-1200, Dec. 2005, doi:10.1109/TPDS.2005.151
Usage of this product signifies your acceptance of the Terms of Use.