Cycle Embedding in Folded Hypercubes with More Faulty Elements

Authors: Wen-Yin Huang, Jia-Jie Liu, Jou-Ming Chang

Abstract:

Faults in a network may take various forms such as hardware/software errors, vertex/edge faults, etc. Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let FFv (respectively, FFe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube FQn. Hsieh et al. have shown that FQn - FFv - FFe for n ≥ 3 contains a fault-free cycle of length at least 2n -2|FFv|, under the constraints that (1) |FFv| + |FFe| ≤ 2n - 4 and (2) every node in FQn is incident to at least two fault-free links. In this paper, we further consider the constraints |FFv| + |FFe| ≤ 2n - 3. We prove that FQn - FFv - FFe for n ≥ 5 still has a fault-free cycle of length at least 2n - 2|FFv|, under the constraints : (1) |FFv| + |FFe| ≤ 2n - 3, (2) |FFe| ≥ n + 2, and (3) every vertex is still incident with at least two links.

Keywords: Folded hypercubes, interconnection networks, cycle embedding, faulty elements.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061322

References:

[1] Ahmed EI-Amawy and Shahram Latifi, Properties and performance of folded hypercubes, IEEE Transactions on Parallel and Distributed Systems, 2(1) (1991) 31-42.
[2] P. Banerjee, J.T. Rahmeh, C. Stunkel, V.S. Nair, K. Roy, V. Balasubramanian, and J.A. Abraham, Algorithm-based fault tolerance on a hypercube multiprocessor, IEEE Transactions on Computers, 39(9) (1990) 1132-1145.
[3] J. Bruck, R. Cypher, and C.T. Ho, Efficient fault-tolerant mesh and hypercube architectures, Proceedings of IEEE Symposium on Fault- Tolerant Computing, 1992, 162-169
[4] Z. Z. Du, J. Jin, M. J. Ma, J. M. Xu, Cycle embedding in hypercubes with faulty vertices and edges, Journal of University of Science and Technology of China, 38(9) (2008) 1020-1024.
[5] J.B. Dugan, S.J. Bavuso, and M.A. Boyd, Dynamic fault-tree models for fault-tolerant computer systems, IEEE Transactions on Reliability, 41(3) (1992) 363-377.
[6] D.R. Duh, G.H. Chen, and J.F. Fang, Algorithms and properties of a new two-level network with folded hypercube as basic modules, IEEE Transactions on Parallel and Distributed Systems, 6(7) (1995) 714-723.
[7] K. Efe, A variation on the hypercube with lower diameter, IEEE Transactions on Computers, 40(11) (1991) 1312-1316.
[8] A. Esfahanian, L.M. Ni, and B.E. Sagan, The twisted n-cube with application to multiprocessing, IEEE Transactions on Computers, 4(1) (1991) 88-93.
[9] Jung-Sheng Fu, Fault-free cycles in folded hypercubes with more faulty elements, Information Processing Letters, 108(5) (2008) 261-263.
[10] Sun-Yuan Hsieh, Some edge-fault-tolerant properties of the folded hypercube, Networks, 51(2) (2008) 92-101.
[11] Sun-Yuan Hsieh and Tzu-Hsiung Shen, Edge-bipancyclicity of a hypercube with faulty vertices and edges, Discrete Applied Mathematics, 156 (2008) 1802-1808.
[12] Sun-Yuan Hsieh, C. N. Kuo, and H. H. Chou, A further result on faultfree cycles in faulty folded hypercubes, Information Processing Letters, 110 (2) (2009) 41-43.
[13] T.L. Kueng, T. Liang, J.J.M. Tan, and L.H. Hsu, Long paths in hypercubes with conditional node-faults, Information Sciences, 179 (2009) 667-681.
[14] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann Publishers Inc., 1992, 78- 82, 239-244.
[15] Y. Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Transactions on Computers, 37(7) (1988) 867-871.
[16] C.H. Tsai and Y.C. Lai, Conditional fault-tolerant edge-bipancyclicity of hypercubes, Information Sciences, 177 (2007) 5590-5597.
[17] D. Wang, Embedding Hamiltonian cycles into folded hypercube with faulty links, Journal of Parallel and Distributed Computing, 61(4) (2001) 545-564.
[18] J. M. Xu, M. J. Ma, Cycles in folded hypercubes, Applied Mathematics Letters, 19(2) (2006) 140-145.
[19] J. M. Xu, M. J. Ma, Z. Z. Du, Edge-fault-tolerant properties of hypercubes and folded hypercubes, Australasian Journal of Combinatorics, 35 (2006) 7-16.
[20] S.G. Ziavras, A versatile family of reduced hypercube interconnection networks, IEEE Transactions on Parallel and Distributed Systems, 5(11) (1993) 1210-1220.