Computer Science ›› 2017, Vol. 44 ›› Issue (11): 264-267.doi: 10.11896/j.issn.1002-137X.2017.11.039

Previous Articles     Next Articles

Sub-network Preclusion in (n,k)-bubble-sort Networks

YANG Yu-xing and QIU Ya-na   

  • Online:2018-12-01 Published:2018-12-01

Abstract: In the real parallel computer systems,faults of processors and links are inevitable,and the fault tolerance abi-lity of a system can be evaluated by the performance of its interconnection network.In order to measure the fault tole-rance abilities of the parallel computers which take (n,k)-bubble-sort networks as underlying topologies,combining the hierarchical structures and sub-network partitions’ characters of (n,k)-bubble-sort networks,an algorithm of the problem that destroy all the (n-m,k-m)-bubble-sort networks in the (n,k)-bubble-sort network under the node fault model and the link fault model was proposed,and the optimal attacking nodes set and the optimal attacking links set were obtained.According to the algorithm,to destroy all the (n-m,k-m)-bubble-sort networks in the (n,k)-bubble-sort network,at least Cmnm!nodes or Cmnm!links ought to be faulty under the node fault model and the link fault mo-del,respectively,where 2≤k≤n-2 and m≤k-1.

Key words: Parallel computer,High-performance interconnection network,(n,k)-bubble-sort network,Fault tolerance,Sub-network preclusion

[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,LIPTK 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!
Full text



No Suggested Reading articles found!