由完全图对换生成的凯莱图的子结构分析

doi:10.15960/j.cnki.issn.1007-6093.2024.04.013

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (4): 135-142.doi: 10.15960/j.cnki.issn.1007-6093.2024.04.013

由完全图对换生成的凯莱图的子结构分析

胡晓敏¹, 张淑蓉¹, 曹婕¹, 杨卫华¹^,*()

1. 太原理工大学数学学院, 山西太原 030024

收稿日期:2022-11-19 出版日期:2024-12-15 发布日期:2024-12-20
通讯作者: 杨卫华 E-mail:ywh222@163.com
基金资助:
国家自然科学基金(12001394);山西省自然科学基金(202103021224058);山西省自然科学基金(202203021212484)

Subnetwork reliability analysis of Cayley graphs generated by complete graphs

Xiaomin HU¹, Shurong ZHANG¹, Jie CAO¹, Weihua YANG¹^,*()

1. College of Mathematics, Taiyuan University of Technology, Taiyuan 030024, Shanxi, China

Received:2022-11-19 Online:2024-12-15 Published:2024-12-20
Contact: Weihua YANG E-mail:ywh222@163.com

摘要/Abstract

摘要：

关于网络子结构可靠性的研究, 对高性能计算机系统的设计和研发有着重要的参考价值, 同时为系统维护提供理论依据。本文从概率故障模型的方法得出了由完全图对换生成的凯莱图的子结构可靠性的上界和下界, 并对理论结果进行了有效性分析。

关键词: 子结构可靠性, 概率故障模型, 凯莱图

Abstract:

The research of subnetwork reliability is valuable for designation and development of high performance computer system, and provides theoretical basis for system maintenance. In this paper, we derive an upper bound and a lower bound of the subnetwork reliability in Cayley graphs generated by complete graphs under the probability fault model. The effectiveness of theoretical results are analyzed.

Key words: subnetwork reliability, probability fault model, Cayley graph

中图分类号:

O157.5

胡晓敏, 张淑蓉, 曹婕, 杨卫华. 由完全图对换生成的凯莱图的子结构分析[J]. 运筹学学报（中英文）, 2024, 28(4): 135-142.

Xiaomin HU, Shurong ZHANG, Jie CAO, Weihua YANG. Subnetwork reliability analysis of Cayley graphs generated by complete graphs[J]. Operations Research Transactions, 2024, 28(4): 135-142.

图/表 3

参考文献 14

1	Chang Y , Bhuyan L . A combinatorial analysis of subcube reliability in hypercube[J]. IEEE Transactions on Computers, 1995, 44, 952- 956. doi: 10.1109/12.392856
2	Wu X L , Latifi S . Substar reliability analysis in star networks[J]. Information Sciences, 2008, 178, 2337- 2348. doi: 10.1016/j.ins.2007.11.015
3	Feng K , Ma X Y , Wei W . Subnetwork reliability analysis of bubble-sort graph networks[J]. Theoretical Computer Science, 2021, 896, 98- 110. doi: 10.1016/j.tcs.2021.10.007
4	冯凯, 马鑫玉. $(n,k)$-冒泡排序网络的子网络可靠性[J]. 计算机科学, 2021, 48 (4): 43- 48.
5	Feng K , Ji Z J , Wei W . Subnetwork reliability analysis in $k$-ary $n$-cubes[J]. Discrete Applied Mathematics, 2019, 267, 85- 92. doi: 10.1016/j.dam.2019.07.003
6	李婧. $k$元$n$方体的子网络可靠性研究[D]. 太原: 山西大学, 2021.
7	Lin L M , Xu L , Zhou S M , et al. The reliability of subgraphs in the arrangement graph[J]. IEEE Transactions on Reliability, 2015, 64, 807- 818. doi: 10.1109/TR.2015.2413372
8	Li X W , Zhou S M , Xu X , et al. The Reliability analysis based on subsystems of $(n,k)$-star graph[J]. IEEE Transactions on Reliability, 2016, 65, 1700- 1709. doi: 10.1109/TR.2016.2570544
9	Huang Y Z , Lin L M , Wang D J . On the reliability of alternating group graph-based networks[J]. Theoretical Computer Science, 2018, 728, 9- 28. doi: 10.1016/j.tcs.2018.03.010
10	Zhang Q F , Xu L Q , Zhou S M , et al. Reliability analysis of subsystem in dual cubes[J]. Theoretical Computer Science, 2020, 816, 249- 259. doi: 10.1016/j.tcs.2020.02.028
11	Zhang Q F , Xu L Q , Zhou S M , et al. Reliability analysis of subsystem in balanced hypercubes[J]. IEEE Access, 2020, 8, 26478- 26486. doi: 10.1109/ACCESS.2020.2971274
12	Oh A D , Choi H A . Generalized measures of fault tolerance in $n$ cube networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1993, 4 (6): 702- 703. doi: 10.1109/71.242153
13	Wu J , Guo G . Fault tolerance measures for $m$-ary $n$-dimensional hypercubes based on forbidden faulty sets[J]. IEEE Transactions on Computers, 1998, 47, 888- 893. doi: 10.1109/12.707589
14	Zhang Z , Xiong W , Yang W H . A kind of conditional fault tolerance of alternating group graphs[J]. Information Processing Letters, 2010, 110, 998- 1002. doi: 10.1016/j.ipl.2010.08.010

$ CK_n $	$\underline{R_{n, n-1}(p)}\geq0$ 所对应的$p$ 的取值范围	$\overline{R_{n, n-1}(p)}\leq 1$ 所对应的$p$ 的取值范围	$\overline{R_{n, n-1}(p)}-\underline{R_{n, n-1}(p)}\leq0.001$ 所对应的$p$ 的取值范围
$ n=4 $	0$ \sim $0.651 4	0$ \sim $0.639 0	0$ \sim $0.426 8
$ n=5 $	0$ \sim $0.880 1	0$ \sim $0.877 0	0$ \sim $0.799 4
$ n=6 $	0$ \sim $0.971 9	0$ \sim $0.971 2	0$ \sim $0.954 5
$ n=7 $	0$ \sim $0.994 9	0$ \sim $0.994 7	0$ \sim $0.992 0
$ n=8 $	0$ \sim $0.999 2	0$ \sim $0.999 2	0$ \sim $0.998 8
$ n=9 $	0$ \sim $0.999 9	0$ \sim $0.999 9	0$ \sim $0.999 8

由完全图对换生成的凯莱图的子结构分析

Subnetwork reliability analysis of Cayley graphs generated by complete graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 14

相关文章 1

编辑推荐

Metrics

本文评价