×
Ge, Huifen; Ye, Chengfu; Zhang, Shumin

The structure fault tolerance of burnt pancake networks. (English) Zbl 07919407

Open Math. 21, Article ID 20230154, 13 p. (2023).

MSC:

05C05 Trees
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C38 Paths and cycles
05C40 Connectivity

Keywords:

interconnection networks; \(H\)-structure connectivity; \(H\)-substructure connectivity; burnt pancake networks
Cite Review PDF
Full Text: DOI
OA License

References:

[1] A. H. Esfahanian and S. L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199, DOI: https://doi.org/10.1016/0020-0190(88)90025-7. · Zbl 0633.05045
[2] J. Fábrega and M. A. Fiol, On the extraconnectivity of graphs, Discrete Appl. Math. 155 (1996), 49-57, DOI: https://doi.org/10.1016/0012-365X(94)00369-T. · Zbl 0857.05064
[3] F. Harary, Conditional connectivity, Networks 13 (1983), no. 3, 347-357, DOI: https://doi.org/10.1002/net.3230130303 · Zbl 0514.05038
[4] C.-K. Lin, L. L. Zhang, J. X. Fan, and D. J. Wang, Structure connectivity and substructure connectivity of hypercubes, Theoret. Comput. Sci. 634 (2016), 97-107, DOI: https://doi.org/10.1016/j.tcs.2016.04.014. · Zbl 1339.68208
[5] S. A. Mane, Structure connectivity of hypercubes, AKCE Int. J. Graphs Comb. 15 (2018), no. 1, 49-52, DOI: https://doi.org/10.1016/J.AKCEJ.2018.01.009. · Zbl 1390.05115
[6] E. Sabir and J. X. Meng, Structure fault tolerance of hypercubes and folded hypercubes, Theoret. Comput. Sci. 711 (2018), 44-55, DOI: https://doi.org/10.1016/j.tcs.2017.10.032. · Zbl 1387.68188
[7] H. Z. Lv and T. Z. Wu, Structure and substructure connectivity of balanced hypercubes, Bull. Malays. Math. Sci. Soc. 43 (2020), 2659-2672, DOI: https://doi.org/10.1007/s40840-019-00827-4. · Zbl 1437.05121
[8] Y. L. Lv, J. X. Fan, D. F. Hsu, and C.-K. Lin, Structure connectivity and substructure connectivity of k-ary n-cube networks, Inf. Sci. 433-434 (2017), 115-124, DOI: https://doi.org/10.1016/j.ins.2017.11.047. · Zbl 1436.68051
[9] G. Z. Zhang and D. J. Wang, Structure connectivity and substructure connectivity of k-ary n-cube networks, IEEE Access 7 (2019), 134496-134504, DOI: https://doi.org/10.1109/ACCESS.2019.2941711.
[10] D. Li, X. L. Hu, and H. Q. Liu, Structure connectivity and substructure connectivity of twisted hypercubes, Theoret. Comput. Sci. 796 (2019), 169-179, DOI: https://doi.org/10.1016/j.tcs.2019.09.007. · Zbl 1436.68251
[11] Z. W. Pan and D. Q. Cheng, Structure connectivity and substructure connectivity of the crossed cube, Theoret. Comput. Sci. 824-825 (2020), 67-80, DOI: https://doi.org/10.1016/j.tcs.2020.04.014. · Zbl 1442.68182
[12] G. Z. Zhang and D. J. Wang, Structure connectivity and substructure connectivity of bubble-sort star graph networks, Appl. Math. Comput. 363 (2019), 124632, DOI: https://doi.org/10.1016/j.amc.2019.124632. · Zbl 1433.68062
[13] C. F. Li, S. W. Lin, and S. J. Li, Structure connectivity and substructure connectivity of star graphs, Discrete Appl. Math. 284 (2020), 472-480, DOI: https://doi.org/10.1016/j.dam.2020.04.009. · Zbl 1443.05105
[14] C. F. Li, S. W. Lin, and S. J. Li, Structure connectivity and substructure connectivity of (n,k)-star graph networks, in: 2018 15th International Symposium on Pervasive Systems, Algorithms and Networks (I-SPAN), Yichang, China, 2018, 240-246, DOI: https://doi.org/10.1109/I-SPAN.2018.00046.
[15] X. W. Li, S. M. Zhou, X. Y. Ren, and X. Guo, Structure and substructure connectivity of alternating group graphs, Appl. Math. Comput. 391 (2021), 125639, DOI: https://doi.org/10.1016/j.amc.2020.125639. · Zbl 1470.05094
[16] L. T. You, Y. J. Han, X. Wang, C. Zhou, R. Gu, and C. Lu, Structure connectivity and substructure connectivity of alternating group graphs, in: 2018 IEEE International Conference on Progress in Informatics and Computing (PIC), Suzhou, China, 2018, pp. 317-321, DOI: https://doi.org/10.1109/PIC.2018.8706296.
[17] W. Feng and S. Y. Wang, Structure connectivity and substructure connectivity of wheel networks, Theoret. Comput. Sci. 850 (2021), 20-29, DOI: https://doi.org/10.1016/j.tcs.2020.10.028. · Zbl 1464.68284
[18] T. T. Chelvam and M. Sivagami, Structure and substructure connectivity of circulant graphs and hypercubes, Arab J. Math. Sci. 27 (2021), no. 1, 94-103, DOI: https://doi.org/10.1016/j.ajmsc.2019.10.001. · Zbl 1488.05249
[19] Q. R. Zhou, S. M. Zhou, J. F. Liu, and X. Q. Liu, Structure and substructure connectivity of divide-and-swap cube, Theoret. Comput. Sci. 880 (2021), 20-36, DOI: https://doi.org/10.1016/j.tcs.2021.05.033. · Zbl 1517.68310
[20] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York, 2007. · Zbl 1134.05001
[21] D. S. Cohen and M. Blum, On the problem of sorting burnt pancakes, Discrete Appl. Math. 61 (1995), 105-120, DOI: https://doi.org/10.1016/0166-218X(94)00009-3. · Zbl 0831.68029
[22] W. H. Gates and C. H. Papadimitriou, Bounds for sorting by prefix reversal, Discrete Math. 27 (1979), 47-49, DOI: https://doi.org/10.1016/0012-365X(79)90068-2. · Zbl 0397.68062
[23] K. A. Haynes, M. L. Broderick, A. D. Brown, T. L. Butner, J. O. Dickson, W. L. Harden, et al., Engineering bacteria to solve the Burnt Pancake problem, J. Biol. Eng. 2 (2008), no. 8, 1-12, DOI: https://doi.org/10.1186/1754-1611-2-8.
[24] A. Labarre and J. Cibulka, Polynomial-time sortable stacks of burnt pancakes, Theoret. Comput. Sci. 412 (2011), 695-702, DOI: https://doi.org/10.1016/j.tcs.2010.11.004. · Zbl 1209.68174
[25] S. A. Blanco, C. Buehrle, and A. Patidar, Cycles in the burnt pancake graph, Discrete Appl. Math. 271 (2019), 1-14, DOI: https://doi.org/10.1016/j.dam.2019.08.008. · Zbl 1428.05129
[26] S. L. Song, X. Y. Li, S. M. Zhou, and M. Chen, Fault tolerance and diagnosability of burnt pancake networks under the comparison model, Theoret. Comput. Sci. 582 (2015), 48-59, DOI: https://doi.org/10.1016/j.tcs.2015.03.027. · Zbl 1309.68021
[27] C. Chin, T.-H. Weng, L.-H. Hsu, and S.-C. Chiou, The spanning connectivity of the burnt pancake graphs, IEICE Trans. Inform. Syst. E92-D (2009), no. 3, 389-400, DOI: https://doi.org/10.1587/transinf.E92.D.389.
[28] T. Iwasaki and K. Kaneko, Fault-tolerant routing in burnt pancake graphs, Inform. Process. Lett. 110 (2010), 535-538, DOI: https://doi.org/10.1016/j.ipl.2010.04.023. · Zbl 1234.68325
[29] P. E. C. Compeau, Girth of pancake graphs, Discrete Appl. Math. 159 (2011), 1641-1645, DOI: https://doi.org/10.1016/j.dam.2011.06.013. · Zbl 1228.05166
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.