星图的强连通度
The Strong Connectivity of Star Graphs
DOI: 10.12677/AAM.2024.133102, PDF, 下载: 37  浏览: 64  国家自然科学基金支持
作者: 张慧英, 王世英*：山西师范大学数学与计算机科学学院，山西 太原
关键词: 互联网络；强连通度；强自然连通度；连通性；星图；Interconnection Network； Strong Connectivity； Strong Nature Connectivity； Star Graph
摘要: 大量数据的处理和复杂问题的解决对多处理器系统的性能要求越来越高，许多多处理器系统都将 互连网络作为底层拓扑结构。 互连网络决定了多处理器系统的性能，在处理器和它们之间通信链 路可能发生故障的系统中，考虑网络的容错性是非常重要的。 传统的点连通性只针对处理器故障， 边连接性只针对通信链路故障的问题。 在此背景下，提出了网络的强连通性，它允许处理器和通 信链路同时故障。 在互连网络的设计中，最基本的考虑因素之一是网络的连通性。 n维星图Sn作为 互连网络的一种有利的拓扑结构，具有许多优良的性质。 因此我们给出了Sn的强连通性以及强自 然连通性。
Abstract: The processing of large amounts of data and the solution of complex problems are increasingly demanding the performance of multiprocessor systems. Many multipro- cessor systems use interconnected networks as the underlying topology. Interconnect networks determine the performance of multiprocessor systems. In systems where processors and the communication links between them are likely to fail, it is impor- tant to consider the fault tolerance of the network. Traditional connectivity is only for processor failure, and edge connectivity is only for communication link failure. In this context, the strong connectivity of the network is proposed, which allows simulta- neous failure of the processor and communication link. One of the most fundamental considerations in the design of an interconnected network is the connectivity of the network. The n-dimensional star graphs Sn has many excellent properties as a favor- able topology for interconnected networks. Therefore, we give the strong connectivity of Sn and strong natural connectivity.
文章引用：张慧英, 王世英. 星图的强连通度[J]. 应用数学进展, 2024, 13(3): 1080-1098. https://doi.org/10.12677/AAM.2024.133102

参考文献

[1] Akers, S.B and Krishnamurthy, B. (1994) A Group-Theoretic Model for Symmetric Intercon- nection Networks. IEEE Transactions on Computers, 38, 555-566.
https://doi.org/10.1109/12.21148
[2] Liu, H., Hu, X. and Gao, S. (2017) The G-Good-Neighbor Conditional Diagnosability of Star Graphs under the PMC and MM* Model. Theoretical Computer Science, 674, 53-59.
https://doi.org/10.1016/j.tcs.2017.02.011
[3] Li, P. and Xu, M. (2019) The t/k-Diagnosability and Strong Menger Connectivity on Star Graphs with Conditional Faults. Theoretical Computer Science, 793, 181-192.
https://doi.org/10.1016/j.tcs.2019.06.016
[4] Ting, T., Zhang, S. and Li, Y. (2023) Hybrid Fault G-Good-Neighbor Conditional Diagnos- ability of Star Graphs. The Journal of Supercomputing, 79, 19297-19311.
https://doi.org/10.1007/s11227-023-05368-z
[5] Eunseuk, O. and Chen, J. (2003) On Strong Menger-Connectivity of Star Graphs. Discrete Applied Mathematics, 129, 499-511.
https://doi.org/10.1016/S0166-218X(02)00600-5
[6] Min, W. and Zhang, Z. (2009) A Kind of Conditional Vertex Connectivity of Star Graphs. Applied Mathematics Letters, 22, 264-267.
https://doi.org/10.1016/j.aml.2008.03.021
[7] Yang, Y. and Wang, S. (2012) Conditional Connectivity of Star Graph Networks under Em- bedding Restriction. Information Sciences, 199, 187-192.
https://doi.org/10.1016/j.ins.2012.02.025
[8] Li, C., Lin, S. and Li, S. (2020) Structure Connectivity and Substructure Connectivity of Star Graphs. Discrete Applied Mathematics, 284, 472-480.
https://doi.org/10.1016/j.dam.2020.04.009
[9] Yang, L., Hua, X. and Yang, Y. (2023) On Structure and Substructure Fault Tolerance of star Networks. The Journal of Supercomputing, 79, 9157-9179.
https://doi.org/10.1007/s11227-022-05036-8
[10] Gu, M., Chang, J. and Hao, R. (2020) On Component Connectivity of Hierarchical Star Networks. International Journal of Foundations of Computer Science, 31, 313-326.
https://doi.org/10.1142/S0129054120500100
[11] Cheng, D. and Guo, D. (2011) Cycle Embedding in Star Graphs with More Conditional Faulty Edges. Applied Mathematics and Computation, 218, 3856-3867.
https://doi.org/10.1016/j.amc.2011.09.033
[12] Xue, S., Deng, Q., Li, P. and Chen, J. (2023) Hamiltonian Paths and Hamiltonian Cycles Passing through Prescribed Linear Forests in Star Graph with Fault-Tolerant Edges. Discrete Applied Mathematics, 334, 68-80.
https://doi.org/10.1016/j.dam.2023.02.016
[13] Wang, S. and Wang, M. (2019) The Strong Connectivity of Bubble-Sort Star Graphs. The Computer Journal, 62, 715-729.
https://doi.org/10.1093/comjnl/bxy077
[14] Cheng, E., Lipman, M.J. and Lipt´ak, L. (2008) Strong Structural Properties of Unidirectional Star Graphs. Discrete Applied Mathematics, 156, 2939-2949.
https://doi.org/10.1016/j.dam.2007.12.005
[15] Zheng, J., Latifi, S., Regentova, E., Luo, K. and Wu, X. (2005) Diagnosability of Star Graphs under the Comparison Diagnosis Model. Information Processing Letters, 93, 29-36.
https://doi.org/10.1016/j.ipl.2004.09.011

为你推荐