×

Fault-free Hamiltonian cycles in crossed cubes with conditional link faults. (English) Zbl 1132.68018

Summary: The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an \(n\)-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to \(2n - 5\) link faults. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its occurrence probability, which is very close to 1.

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ashir, Y. A.; Stewart, I. A., Fault-tolerant embedding of Hamiltonian circuits in \(k\)-ary \(n\)-cube, SIAM Journal on Discrete Mathematics, 15, 3, 317-328 (2002) · Zbl 1018.68058
[2] Chan, M. Y.; Lee, S. J., On the existence of Hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics, 4, 4, 511-527 (1991) · Zbl 0747.05035
[3] Chang, C. P.; Sung, T. Y.; Hsu, L. H., Edge congestion and topological properties of crossed cube, IEEE Transactions on Parallel and Distributed Systems, 11, 1, 64-80 (2000)
[4] Chang, G. Y.; Chen, G. H.; J Chang, G., \((t,k)\)-Diagnosis for matching composition networks, IEEE Transactions on Computers, 55, 1, 88-92 (2006)
[5] Day, K., The conditional node connectivity of the \(k\)-ary \(n\)-cube, Journal of Interconnection Networks, 5, 1, 13-26 (2004)
[6] Efe, K., A variation on the hypercube with lower diameter, IEEE Transactions on Computers, 40, 11, 1312-1316 (1991)
[7] Efe, K., The crossed cube architecture for parallel computation, IEEE Transactions on Parallel and Distributed Systems, 3, 5, 513-524 (1992)
[8] Efe, K.; Blackwell, P. K.; Slough, W.; Shiau, T., Topological properties of the crossed cube architecture, Parallel Computing, 20, 1763-1775 (1994) · Zbl 0875.68162
[9] Esfahanian, A. H., Generalized measures of fault-tolerance with application to \(n\)-cube networks, IEEE Transactions on Computers, 38, 11, 1586-1591 (1989)
[10] Esfahanian, A. H.; Hakimi, S. L., On computing a conditional edge-connectivity of a graph, Information Processing Letters, 27, 195-199 (1988) · Zbl 0633.05045
[11] Fan, J.; Jia, X.; Lin, X., Complete path embedding in crossed cubes, Information Sciences, 176, 22, 3332-3346 (2005) · Zbl 1101.68004
[12] Fan, J.; Lin, X.; Jia, X., Optimal path embedding in crossed cube, IEEE Transactions on Parallel and Distributed Systems, 16, 12, 1190-1200 (2005)
[13] Fan, J.; Lin, X., The \(t/k\)-diagnosability of the BC graphs, IEEE Transactions on Computers, 54, 2, 176-184 (2005)
[14] Fäbrega, J.; Fiol, M. A., Extraconnectivity of graphs with large girth, Discrete Mathematics, 127, 163-170 (1994) · Zbl 0797.05058
[15] Fu, J. S., Longest fault-free paths in hypercubes with vertex faults, Information Sciences, 176, 7, 759-771 (2006) · Zbl 1088.68019
[16] Harary, F., Conditional connectivity, Networks, 13, 347-357 (1983) · Zbl 0514.05038
[17] Huang, W. T.; Chuang, Y. C.; Hsu, L. H.; Tan, J. M., On the fault-tolerant hamiltonicity of crossed cubes, IEICE Transactions on Fundamentals, E85-A, 6, 1359-1371 (2002)
[18] H.S. Hung, J.S. Fu, G.H. Chen, Embedding fault-free cycles in crossed cubes with conditional link faults, in preparation.; H.S. Hung, J.S. Fu, G.H. Chen, Embedding fault-free cycles in crossed cubes with conditional link faults, in preparation. · Zbl 1132.68018
[19] Kulasinghe, P.; Betayeb, S., Embedding binary trees into crossed cubes, IEEE Transactions on Computers, 44, 7, 923-929 (1995) · Zbl 1053.68585
[20] Kulasinghe, P., Connectivity of the crossed cube, Information Processing Letters, 61, 221-226 (1997) · Zbl 1336.68008
[21] Latifi, S., Combinatorial analysis of the fault-diameter of the \(n\)-cube, IEEE Transactions on Computers, 42, 1, 27-33 (1993) · Zbl 1395.68054
[22] Park, C. D.; Chwa, K. Y., Hamiltonian properties on the class of hypercube-like networks, Information Processing Letters, 91, 11-17 (2004) · Zbl 1178.68043
[23] Qiao, L.; Yi, Z., Restricted connectivity and restricted fault diameter of some interconnection networks, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 21 (1995) · Zbl 0864.05056
[24] Rouskov, Y.; Latifi, S.; Srimani, P. K., Conditional fault diameter of star graph networks, Journal of Parallel and Distributed Computing, 33, 91-97 (1996)
[25] Saad, Y.; Schultz, M. H., Topological properties of hypercubes, IEEE Transactions on Computers, 37, 7, 867-872 (1988)
[26] Tsai, C. H., Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Computer Science, 314, 431-443 (2004) · Zbl 1072.68082
[27] A.S. Vaidya, P.S.N. Rao, S.R. Shankar, A class of hypercube-like networks, in: Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, Los Alamitos, CA, 1993, pp. 800-803.; A.S. Vaidya, P.S.N. Rao, S.R. Shankar, A class of hypercube-like networks, in: Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, Los Alamitos, CA, 1993, pp. 800-803.
[28] Wu, A. Y., Embedding of tree networks into hypercubes, Journal of Parallel and Distributed Computing, 2, 3, 23-249 (1985)
[29] Yang, M. C.; Li, T. K.; Tan, J. M.; Hsu, L. H., Fault-tolerant cycle-embedding of crossed cubes, Information Processing Letters, 88, 149-154 (2003) · Zbl 1178.68092
[30] Yang, M. C.; Li, T. K.; Tan, J. M.; Hsu, L. H., On embedding cycles into faulty twisted cubes, Information Sciences, 176, 6, 676-690 (2006) · Zbl 1103.68028
[31] Zhu, Q.; Xu, J. M.; Lü, M., Edge fault tolerance analysis of a class of networks, Applied Mathematics and Computation, 172, 1, 111-121 (2006) · Zbl 1088.68022
[32] Zhu, Q.; Xu, J. M.; Hou, X.; Xu, M., On reliability of the folded hypercubes, Information Sciences, 177, 8, 1782-1788 (2007) · Zbl 1115.68034
[33] http://inrg.csie.ntu.edu.tw/CQ_Hamiltonian/index.htm; http://inrg.csie.ntu.edu.tw/CQ_Hamiltonian/index.htm
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.