计算机科学 ›› 2017, Vol. 44 ›› Issue (11): 264-267.doi: 10.11896/j.issn.1002-137X.2017.11.039
杨玉星,邱亚娜
YANG Yu-xing and QIU Ya-na
摘要: 在并行计算机系统中,元器件和线路故障普遍存在,而系统的容错能力可以通过其底层基础网络的拓扑性质衡量。为了精确度量以k元n维冒泡排序网络为底层拓扑结构的并行计算机系统的容错能力,结合其层次结构和子网划分特征,分别提出了节点故障模型和线路故障模型下攻击该网络中所有k-m元n-m维冒泡排序子网络的算法,确定了需要攻击的最优节点集合和最优线路集合。根据算法可得:当2≤k≤n-2,m≤k-1时,攻击k元n维冒泡排序网络中所有的k-m元n-m维冒泡排序子网络,在节点故障模型下需要攻击至少Cmnm!个节点,在边故障模型下需要攻击至少Cmnm!条线路。
[1] LATIFI S.A study of fault tolerance in star graph [J].Information Processing Letters,2007,102(5):196-200. [2] LATIFI S,SABERINIA E,WU X.Robustness of star graphnetwork under link failure[J].Information Sciences,2008,178 (3):802-806. [3] WALKER D,LATIFI S.Improving bounds on link failure tole-rance of the star graph [J].Information Sciences,2010,180(13):2571-2575. [4] WANG S,YANG Y.Fault tolerance in bubble-sort graph networks [J].Theoretical Computer Science,2012,421:62-69. [5] YANG Y X,WANG S Y.Recursive algorithm for k-cycle preclusion problem in k-ary n-cubes [J].Journal of Computer Applications,2013,3(9):2401-2403.(in Chinese) 杨玉星,王世英.k元n立方网络的k圈排除问题的递归算法[J].计算机应用,2013,33(9):2401-2403. [6] YANG Y,WANG S,LI J.Subnetwork preclusion for bubble-sort networks [J].Information Processing Letters,2015,115(1):817-821. [7] WANG S,ZHANG G,FENG K.Fault tolerance in k-ary n-cube networks [J].Theoretical Computer Science,2012,460:34-41. [8] WANG S,FENG K.Fault tolerance in the arrangement graphs [J].Theoretical Computer Science,2014,533:64-71. [9] FENG K,WANG S,ZHANG G.Link failure tolerance in the arrangement graphs [J].International Journal of Foundations of Computer Science,2015,26(2):241-254. [10] WANG M,YANG W,GUO Y,et al.Conditional fault tolerance in a class of Cayley graphs [J].International Journal of Compu-ter Mathematics,2016,93(1):678-682. [11] SHAWASH N.Relationships among popular interconnectionnetworks and their common generalization [D].Oakland,USA:Oakland University,2008. [12] CHENG E,LIPTK L,SHERMAN D.Matching preclusion for the (n,k)-bubble-sort graphs [J].International Journal of Computer Mathematics,2010,87(11):2408-2418. [13] BONDY J A,MURTY U S R.Graph Theory [M].New York:Springer Press,2008:624-626. |
No related articles found! |
|