|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|