Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (3) : 153104    https://doi.org/10.1007/s11704-020-9387-3
RESEARCH ARTICLE
Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes
Weibei FAN1, Jianxi FAN2(), Zhijie HAN3, Peng LI1, Yujie ZHANG1, Ruchuan WANG3
1. College of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
2. School of Computer Science and Technology, Soochow University, Suzhou 215006, China
3. Jiangsu High Technology Research Key Laboratory forWireless Sensor Networks, Jiangsu Province, Nanjing 210003, China
 Download: PDF(1102 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by (s + t + 1)-dimensional LeTQs,t, which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQs,t has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQs,t − ( fv + fe), with faulty vertices fv and faulty edges fe. Firstly, we prove that an LeTQs,t can tolerate up to s−1 faulty vertices and edges when embedding a Hamiltonian cycle, for s≥2, t≥3, and s≤t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQs,twith up to (s − 2) faulty vertices and edges. That is, we show that LeTQs,t is (s−1)-Hamiltonian and (s−2)- Hamiltonian-connected. The results are proved to be optimal in this paper with at most (s − 1)-fault-tolerant Hamiltonicity and (s − 2) fault-tolerant Hamiltonian connectivity of LeTQs,t.

Keywords interconnection network      fault-tolerant      LeTQs,t      hamiltonian cycle      hamiltonian path     
Corresponding Author(s): Jianxi FAN   
Just Accepted Date: 26 March 2020   Issue Date: 11 March 2021
 Cite this article:   
Weibei FAN,Jianxi FAN,Zhijie HAN, et al. Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes[J]. Front. Comput. Sci., 2021, 15(3): 153104.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-9387-3
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I3/153104
1 L M Lin, S Y Hsieh, L Xu, S M Zhou, R Q Chen. The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model. Journal of Computer System and Sciences, 2018, 95: 1–18
https://doi.org/10.1016/j.jcss.2017.11.004
2 L Guo. Reliability analysis of twisted cubes. Theoretical Computer Science, 2018, 707: 96–101
https://doi.org/10.1016/j.tcs.2017.10.016
3 L M Lin, S Y Hsieh, R Q Chen, L Xu, C W Lee. The relationship between g-restricted connectivity and g-good-neighbor fault diagnosability of general regular networks. IEEE Transactions on Reliability, 2018, 67(1): 285–296
https://doi.org/10.1109/TR.2017.2760905
4 D Wang. Hamiltonian embedding in crossed cubes with failed links. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(11): 2117–2124
https://doi.org/10.1109/TPDS.2012.30
5 J Fan, X Jia, X Lin. Embedding of cycles in twisted cubes with edgepancyclic. Algorithmica, 2008, 51(3): 264–282
https://doi.org/10.1007/s00453-007-9024-7
6 Z Liu, J Fan, J Zhou, B Cheng, X Jia. Fault-tolerant embedding of complete binary trees in locally twisted cubes. Journal of Parallel and Distributed Computing, 2017, 101: 69–78
https://doi.org/10.1016/j.jpdc.2016.11.005
7 C C Wei, S Y Hsieh. h-Restricted connectivity of locally twisted cubes. Discrete Applied Mathematics, 2017, 217: 330–339
https://doi.org/10.1016/j.dam.2016.08.012
8 Y Huang, L Lin, D Wang, L Xu. Minimum neighborhood of alternating group graphs. IEEE Access, 2019, 7: 17299–17311
https://doi.org/10.1109/ACCESS.2019.2896101
9 Y Zhai, L Lin, L Xu, X Zhang, Y Huang. The conditional diagnosability with g-good-neighbor of exchanged hypercubes. The Computer Journal, 2019, 62(5): 747–756
https://doi.org/10.1093/comjnl/bxy083
10 D F Zhou, J X Fan, C K Lin, B L Cheng, J Y Zhou, Z Liu. Optimal path embedding in the exchanged crossed cube. Journal of Computer Science and Technology, 2017, 32 (3): 618–629
https://doi.org/10.1007/s11390-017-1729-8
11 Y Ren, S Wang. The g-good-neighbour diagnosability of locally twisted cubes. Theoretical Computer Science, 2017, 697: 91–97
https://doi.org/10.1016/j.tcs.2017.07.030
12 X Yang, D J Evans, G M Megson. The locally twisted cubes. International Journal of Computer Mathematics, 2005, 82(4): 401–413
https://doi.org/10.1080/0020716042000301752
13 W B Fan, J X Fan, C K Lin, G J Wang, B L Cheng, R C Wang. An efficient algorithm for embedding exchanged hypercubes into grids. The Journal of Supercomputing, 2019, 75(2): 783–807
https://doi.org/10.1007/s11227-018-2612-2
14 P K K Loh, W J Hsu, Y Pan. The exchanged hypercube. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866–874
https://doi.org/10.1109/TPDS.2005.113
15 Z Zhang, Y Deng, G Min, J Xie, S Huang. ExCCC-DCN: a highly scalable, cost-effective and energy-efficient data center structure. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(4): 1046–1060
https://doi.org/10.1109/TPDS.2016.2609428
16 J M Chang, X R Chen, J S Yang, R Y Wu. Locally exchanged twisted cubes: connectivity and super connectivity. Information Processing Letters, 2016, 116(7): 460–466
https://doi.org/10.1016/j.ipl.2016.03.003
17 W B Fan, J X Fan, C K Lin, Y Wang, Y J Han, R C Wang. Optimally embedding 3-ary n-cubes into grids. Journal of Computer Science and Technology, 2019, 34(2): 372–387
https://doi.org/10.1007/s11390-019-1893-0
18 L M Lin, L Xu, S M Zhou, S Y Hsieh. The t/k-Diagnosability for regular networks. IEEE Transactions on Computers, 2016, 65(10): 3157–3170
https://doi.org/10.1109/TC.2015.2512866
19 L M Lin, L Xu, S M Zhou, S Y Hsieh. The extra, restricted connectivity and conditional diagnosability of split-star networks. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2): 533–545
https://doi.org/10.1109/TPDS.2015.2400459
20 E Cheng, K Qiu, S Shen. Diagnosability problems of the exchanged hypercube and its generalization. International Journal of Computer Mathematics: Computer Systems Theory, 2017, 2(2): 39–52
https://doi.org/10.1080/23799927.2017.1323799
21 E Cheng, K Qiu, Z Shen. A strong connectivity property of the generalized exchanged hypercube. Discrete Applied Mathematics, 2017, 216: 529–536
https://doi.org/10.1016/j.dam.2015.11.014
22 L Guo, G Su, W Lin, J Chen. Fault tolerance of locally twisted cubes. Applied Mathematics and Computation, 2018, 334: 401–406
https://doi.org/10.1016/j.amc.2018.03.107
23 L Guo, X Guo. Fault tolerance of hypercubes and folded hypercubes. The Journal of Supercomputing, 2014, 68(3): 1235–1240
https://doi.org/10.1007/s11227-013-1078-5
24 C C Wei, C A Chen, S Y Hsieh. Conditional (t, k)-diagnosis in regular and irregular graphs under the comparison diagnosis model. IEEE Transactions on Dependable Security and Computation, 2018, 15(2): 351–356
https://doi.org/10.1109/TDSC.2016.2585489
25 L M Lin, L Xu, S M Zhou, Y Xiang, Trustworthiness-hypercube-based reliable communication in mobile social networks. Information Sciences, 2016, 369: 34–50
https://doi.org/10.1016/j.ins.2016.05.048
26 Y Huang, L Lin, D Wang. On the reliability of alternating group graphbased networks. Theoretical Computer Science, 2018, 728: 9–28
https://doi.org/10.1016/j.tcs.2018.03.010
27 X Li, B Liu, M Ma, J Xu. Many-to-many disjoint paths in hypercubes with faulty vertices. Discrete Applied Mathematics, 2017, 217: 229–242
https://doi.org/10.1016/j.dam.2016.09.013
28 H Lu, F Wang. Hamiltonian paths passing through prescribed edges in balanced hypercubes. Theoretical Computer Science, 2019, 761: 23–33
https://doi.org/10.1016/j.tcs.2018.08.017
29 H Liu, X Hu, S Gao. Hamiltonian cycles and paths in faulty twisted hypercubes. Discrete Applied Mathematics, 2019, 257: 243–249
https://doi.org/10.1016/j.dam.2018.10.011
30 X Xu, Y Huang, P Zhang, S Zhang. Fault-tolerant vertex-pancyclicity of locally twisted cubes LTQn. Journal of Parallel and Distributed Computing, 2016, 88: 57–62
31 D Cheng, R Hao. Various cycles embedding in faulty balanced hypercubes. Information Sciences, 2015, 297: 140–153
https://doi.org/10.1016/j.ins.2014.11.008
32 C W Cheng, S Y Hsieh. Fault-tolerant cycle embedding in cartesian product graphs: edge-pancyclicity and edge-bipancyclicity with faulty edges. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(11): 2997–3011
https://doi.org/10.1109/TPDS.2014.2364604
33 Y L Lv, C K Lin, J X Fan, X H Jia. Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K1,3-structure faults. Journal of Parallel and Distributed Computing, 2018, 120: 148–158
https://doi.org/10.1016/j.jpdc.2018.06.007
34 M R Garey, D S Johnson. Computers and Intractability: a Guide to The Theory of NP-Completeness. United States of America: W. H. Freeman and Company, 1979
35 S Y Hsieh, C Y Wu. Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults. Journal of Combinatorial Optimization, 2010, 19(1): 16–30
https://doi.org/10.1007/s10878-008-9157-x
36 X Xu, W Zhai, J Xu, A Deng, Y Yang. Fault-tolerant edge-pancyclicity of locally twisted cubes. Information Sciences, 2011, 181(11): 2268–2277
https://doi.org/10.1016/j.ins.2011.01.031
[1] Article highlights Download
[1] Wenhao ZHOU,Juan CHEN,Chen CUI,Qian WANG,Dezun DONG,Yuhua TANG. Detailed and clock-driven simulation for HPC interconnection network[J]. Front. Comput. Sci., 2016, 10(5): 797-811.
[2] Xianpeng HUANGFU, Deke GUO, Honghui CHEN, Xueshan LUO. KMcube: the compound of Kautz digraph and M?bius cube[J]. Front Comput Sci, 2013, 7(2): 298-306.
[3] YANG Xuejun, YI Huizhan, QU Xiangli, ZHOU Haifang. Compiler-directed power optimization of high-performance interconnection networks for load-balancing MPI applications[J]. Front. Comput. Sci., 2007, 1(1): 94-105.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed