Abstract
The crossed cube, which is a variation of the hypercube, possesses some properties that are superior to those of the hypercube. In this paper, we show that with the assumption of each node incident with at least two fault-free links, an n-dimensional crossed cube with up to 2n−5 link faults can embed, with dilation one, fault-free cycles of lengths ranging from 4 to 2n. The assumption is meaningful, for its occurrence probability is very close to 1, and the result is optimal with respect to the number of link faults tolerated. Consequently, it is very probable that algorithms executable on rings of lengths ranging from 4 to 2n can be applied to an n-dimensional crossed cube with up to 2n−5 link faults.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alspach B, Hare D (1991) Edge-pancyclic block-intersection graphs. Discrete Math 97:17–24
Araki T (2003) Edge-pancyclicity of recursive circulants. Inf Process Lett 88:287–292
Ashir YA, Stewart IA (2002) Fault-tolerant embedding of Hamiltonian circuits in k-ary n-cube. SIAM J Discrete Math 15(3):317–328
Chan MY, Lee SJ (1991) On the existence of Hamiltonian circuits in faulty hypercubes. SIAM J Discrete Math 4(4):511–527
Chang CP, Sung TY, Hsu LH (2000) Edge congestion and topological properties of crossed cube. IEEE Trans Parallel Distrib Syst 11(1):64–80
Day K (2004) The conditional node connectivity of the k-ary n-cube. J Interconnect Netw 5(1):13– 26
Efe K (1991) A variation on the hypercube with lower diameter. IEEE Trans Comput 40(11):1312–1316
Efe K (1992) The crossed cube architecture for parallel computation. IEEE Trans Parallel Distrib Syst 3(5):513–524
Esfahanian AH (1989) Generalized measures of fault-tolerance with application to n-cube networks. IEEE Trans Comput 38(11):1586–1591
Fan J, Lin X, Jia X (2005) Node-pancyclicity and edge-pancyclicity of crossed cube. Inf Processing Lett 93:133–138
Fu JS, Chen GH (2004) Fault-tolerant cycle embedding in hierarchical cubic networks. Networks 43(1):28–38
Fu JS (2007) Conditional fault-tolerant Hamiltonicity of star graphs. Parallel Comput 33:488–496
Harary F (1983) Conditional connectivity. Networks 13:347–357
Huang WT, Chuang YC, Hsu LH, Tan JM (2002) On the fault-tolerant Hamiltonicity of crossed cubes. IEICE Trans Fundam E85-A(6):1359–1371
Hung HS, Fu JS, Chen GH (2007) Fault-free Hamiltonian cycles in crossed cubes with conditional link faults. Inf Sci 177:5664–5674
Kulasinghe P, Betayeb S (1995) Embedding binary trees into crossed cubes. IEEE Trans Comput 44(7):923–929
Kulasinghe P (1997) Connectivity of the crossed cube. Inf Process Lett 61:221–226
Latifi S (1993) Combinatorial analysis of the fault-diameter of the n-cube. IEEE Trans Comput 42(1):27–33
Lih KW, Zengmin S, Weifan W, Kemin Z (2002) Edge-pancyclicity of coupled graphs. Discrete Appl Math 119:259–264
Qiao L, Yi Z (1995) Restricted connectivity and restricted fault diameter of some interconnection networks. DIMACS Ser Discrete Math Theor Comput Sci 21:267–273
Rouskov Y, Latifi S, Srimani PK (1996) Conditional fault diameter of star graph networks. J Parallel Distrib Comput 33:91–97
Saad Y, Schultz MH (1988) Topological properties of hypercubes. IEEE Trans Comput 37(7):867–872
Tsai CH (2004) Linear array and ring embeddings in conditional faulty hypercubes. Theor Comput Sci 314:431–443
Wu AY (1985) Embedding of tree networks into hypercubes. J Parallel Distrib Comput 2(3):23–249
Xu M, Xu JM (2005) Edge-pancyclicity of Möbius cube. Inf Process Lett 93:131–138
Yang MC, Li TK, Tan JM, Hsu LH (2003) Fault-tolerant cycle-embedding of crossed cubes. Inf Process Lett 88:149–154
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fu, JS., Hung, HS. & Chen, GH. Embedding fault-free cycles in crossed cubes with conditional link faults. J Supercomput 49, 219–233 (2009). https://doi.org/10.1007/s11227-008-0232-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-008-0232-y