×

Fault-tolerant edge-pancyclicity of locally twisted cubes. (English) Zbl 1216.68058

Summary: The \(n\)-dimensional locally twisted cube \(\text{LTQ}_{n}\) is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of \(\text{LTQ}_{n}\), and shows that if \(\text{LTQ}_{n}\) (\(n \geqslant 3\)) contains at most \(n - 3\) faulty vertices and/or edges then, for any fault-free edge \(e\) and any integer \(\ell \) with \(6 \leqslant \ell \leqslant 2^{n} - f_{v}\), there is a fault-free cycle of length \(\ell \) containing the edge \(e\), where \(f_{v}\) is the number of faulty vertices. The result is optimal in some sense. The proof is based on the recursive structure of \(\text{LTQ}_{n}\).

MSC:

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

References:

[1] Akl, S. G., Parallel Computation: Models and Methods (1997), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ
[2] Araki, T.; Kikuchi, Y., Hamiltonian laceability of bubble-sort graphs with edge faults, Inform. Sci., 177, 13, 2679-2691 (2007) · Zbl 1115.68106
[3] Andre, F.; Verjus, J. P., Hypercubes and Distributed Computers (1989), Horth-Halland: Horth-Halland Amsterdam, New York, Oxford
[4] Chang, Q.-Y.; Ma, M.-J.; Xu, J.-M., Fault-tolerant pancyclicity of locally twisted cubes (in Chinese), J. China Univ. Sci. Tech., 36, 6, 607-610 (2006)
[5] Choudum, S. A.; Sunitha, V., Augmented cubes, Networks, 40, 2, 71-84 (2002) · Zbl 1019.05052
[6] Cull, P.; Larson, S. M., The Möbius cubes, IEEE Trans. Comput., 44, 5, 647-659 (1995) · Zbl 1041.68522
[7] Efe, K., A variation on the hypercube with lower diameter, IEEE Trans. Comput., 40, 11, 1312-1316 (1991)
[8] Fan, J.; Jia, X.; Lin, X., Complete path embeddings in crossed cubes, Inform. Sci., 176, 22, 3332-3346 (2006) · Zbl 1101.68004
[9] Fu, J.-S., Longest fault-free paths in hypercubes with vertex faults, Inform. Sci., 176, 759-771 (2006) · Zbl 1088.68019
[10] Y.-J. Han, J.-X. Fan, J.-W. Yang, Path embedding in faulty locally twisted cubes, in: Second IEEE International Conference on Computer Science and Information Technology, 2009, pp. 214-218.; Y.-J. Han, J.-X. Fan, J.-W. Yang, Path embedding in faulty locally twisted cubes, in: Second IEEE International Conference on Computer Science and Information Technology, 2009, pp. 214-218.
[11] Han, Y.-J.; -X Fan, J.; Zhang, S.-K.; -W Yang, J.; Qian, P.-D., Embedding meshes into locally twisted cubes, Inform. Sci., 180, 3794-3805 (2010) · Zbl 1205.68036
[12] Hayes, P. P.; Mudge, T. N., Hypercube supercomputers, Proc. IEEE, 77, 12, 1829-1841 (1989)
[13] P.A.J. Hilbers, M.R.J. Koopman, J.L.A. van de Snepscheut, The twisted cubes, in Parallel Architectures and Languages Europe, Lecture Notes in Computer Science, June 1987, pp.152-159.; P.A.J. Hilbers, M.R.J. Koopman, J.L.A. van de Snepscheut, The twisted cubes, in Parallel Architectures and Languages Europe, Lecture Notes in Computer Science, June 1987, pp.152-159.
[14] Hillis, W. D., The Connection Machine (1985), MIT Press: MIT Press Cambridge, Mass
[15] Hsieh, S.-Y.; Lee, C.-W., Conditional edge-fault hamiltonicity of matching composition networks, IEEE Trans. Parallel Distrib. Syst., 20, 4, 581-592 (2009)
[16] Hsieh, S.-Y.; Shen, T.-H., Edge-bipancyclicity of a hypercube with faulty vertices and edges, Discrete Appl. Math., 156, 10, 1802-1808 (2008) · Zbl 1152.05338
[17] Hsieh, S.-Y.; Shiu, J.-Y., Cycle embedding of augmented cubes, Appl. Math. Comput., 191, 314-319 (2007) · Zbl 1193.05098
[18] Hsieh, S.-Y.; Tu, C.-J., Constructing edge-disjoint spanning trees in locally twisted cubes, Theor. Comput. Sci., 410, 926-932 (2009) · Zbl 1162.68046
[19] Hsieh, S.-Y.; Wu, C.-Y., Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults, J. Comb. Optim., 19, 16-30 (2010) · Zbl 1185.90029
[20] Hu, K.-S.; Yeoh, S.-S.; Chen, C.-Y.; Hsu, L.-H., vertex-pancyclicity and edge-pancyclicity of hypercube variants, Inform. Process. Lett., 102, 1, 1-7 (2007) · Zbl 1185.05089
[21] Kueng, T.-L.; Liang, T.; Hsu, L.-H.; Tan, J. J.M., Long paths in hypercubes with conditional node-faults, Inform. Sci., 179, 5, 667-681 (2009) · Zbl 1170.68001
[22] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, California · Zbl 0743.68007
[23] Li, T.-K.; Tan, J. J.M.; Hsu, L.-H., Hyper hamiltonian laceability on edge fault star graph, Inform. Sci., 165, 1-2, 59-71 (2004) · Zbl 1057.05054
[24] Lin, J.-C.; Yang, J.-S.; Hsu, C.-C.; Chang, J.-M., Hyper hamiltonian laceability on edge fault star graph, Information Processing Letters, 110, 414-419 (2010)
[25] Y.-J. Liu, W.Y. Chou, J.K. Lan, C.Y. Chen, Constructing independent spanning trees for hypercubes and locally twisted cubes, in: Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009), Kaohsiung, Taiwan, 2009, pp. 17-22.; Y.-J. Liu, W.Y. Chou, J.K. Lan, C.Y. Chen, Constructing independent spanning trees for hypercubes and locally twisted cubes, in: Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009), Kaohsiung, Taiwan, 2009, pp. 17-22.
[26] Ma, M.-J.; Xu, J.-M., Panconnectivity of locally twisted cubes, Appl. Math. Lett., 19, 7, 681-685 (2006) · Zbl 1118.05050
[27] Ma, M.-J.; Xu, J.-M., Weak Edge-pancyclicity of locally twisted cubes, Ars Comb., 89, 89-94 (2008) · Zbl 1224.05262
[28] Nugent, S. F., The iPDC/2 direct-connect communication technology, Proc. Conf. Hypercube Concurrent Comput. Appl., 1, 51-60 (1988)
[29] Parhami, B., Introduction to Parallel Processing: Algorithms and Architectures (1999), Plenum: Plenum New York
[30] Park, J.-H.; Lim, H.-S.; Kim, H.-C., Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theor. Comput. Sci., 377, 170-180 (2007) · Zbl 1115.68116
[31] Seitz, C. L., The cosmic cube, Commun. Assoc. Comput. Machinery, 28, 1, 22-33 (1985)
[32] H. Sullivan, T.R. Bashkow, A scale homogeneous full distributed parallel machine, in: Proceeding of the Annual Symposium on Computer Architecture, 1977, pp. 105-117.; H. Sullivan, T.R. Bashkow, A scale homogeneous full distributed parallel machine, in: Proceeding of the Annual Symposium on Computer Architecture, 1977, pp. 105-117.
[33] Tsai, C.-H., Embedding various even cycles in the hypercube with mixed link and node failures, Appl. Math. Lett., 21, 8, 855-860 (2008) · Zbl 1155.68017
[34] Tsai, C.-H.; Lai, Y.-C., Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Sci., 177, 24, 5590-5597 (2007) · Zbl 1132.68019
[35] Wang, H.-L.; Wang, J.-W.; Xu, J.-M., Edge-fault-tolerant bipanconnectivity of hypercubes, Inform. Sci., 179, 4, 404-409 (2009) · Zbl 1163.68314
[36] Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers.: Kluwer Academic Publishers. Dordrecht/Boston/London · Zbl 1046.68026
[37] Xu, J.-M.; Ma, M.-J., Survey on path and cycle embedding in some networks, Front. Math. China, 4, 2, 217-252 (2009) · Zbl 1176.90081
[38] Xu, J.-M.; Wang, J.-W.; Wang, W.-W., Super and restricted connectivity of some interconnection networks, Ars Comb., 94, 25-32 (2010) · Zbl 1240.05177
[39] Yang, H.; Yang, X. F., A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM* model, Comput. Math. Appl., 53, 918-926 (2007) · Zbl 1147.68409
[40] Yang, X. F.; Megson, G. M.; Evans, D. J., Locally twisted cubes are 4-pancyclic, Appl. Math. Lett., 17, 919-925 (2004) · Zbl 1056.05074
[41] Yang, X. F.; Evans, D. J.; Megson, G. M., The locally twisted cubes, Inter. J. Comput. Math., 82, 4, 401-413 (2005) · Zbl 1097.68522
[42] Yang, M.-C.; Li, T.-K.; Tan, J. J.M.; Hsu, L.-H., On embedding cycles into faulty twisted cubes, Inform. Sci., 176, 6, 676-690 (2006) · Zbl 1103.68028
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.