Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (9): 2454-2456.DOI: 10.11772/j.issn.1001-9081.2017.09.2454

Previous Articles     Next Articles

Conditional strong matching preclusion for k-ary n-cubes

FENG Kai   

  1. School of Computer & Information Technology, Shanxi University, Taiyuan Shanxi 030006, China
  • Received:2017-03-10 Revised:2017-04-27 Online:2017-09-10 Published:2017-09-13
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61502286).



  1. 山西大学 计算机与信息技术学院, 太原 030006
  • 通讯作者: 冯凯,
  • 作者简介:冯凯(1987-),男,山西临汾人,讲师,博士,CCF会员,主要研究方向:互连网络的容错性、图论及其应用。
  • 基金资助:

Abstract: To measure the ability of k-ary n-cube to remain the property of having a perfect matching or an almost perfect matching in the presence of failures, by analysis of constructions of the fault sets that make the k-ary n-cube having neither a perfect matching nor an almost perfect matching under the conditional fault model, the minimum number of failures that make the k-ary n-cube unmatchable under the conditional fault model was studied. When k ≥ 4 is even and n ≥ 2, the exact value of the fault-tolerant parameter for k-ary n-cube was obtained and all the corresponding minimum fault sets were characterized. When k ≥ 3 is an odd number and n ≥ 2, a sharp lower bound and a sharp upper bound on the fault tolerance parameter for k-ary n-cube were given. The results indicate that the parallel computer system, which takes the k-ary n-cube with odd k as underlying interconnection topology, has good ability to remain the property of having a perfect matching or an almost perfect matching under the conditional fault model. Moreover, this system is still matchable if the number of failures does not exceed 2n and at most 4n-3 failures could make this system unmatchable.

Key words: parallel computer system, interconnection network, k-ary n-cube, perfect matching, conditional failure

摘要: 为了度量发生故障时kn方体对其可匹配性的保持能力,通过剖析条件故障下使得kn方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得kn方体不可匹配所需的最小故障数。当k ≥ 4为偶数且n ≥ 2时,得出了kn方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当k ≥ 3为奇数且n ≥ 2时,给出了该kn方体容错性参数的一个可达下界和一个可达上界。结果表明,选取k为奇数的kn方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2n时仍是可匹配的,要使该系统不可匹配至多需要4n-3个故障元。

关键词: 并行计算机系统, 互连网络, kn方体, 完美匹配, 条件故障

CLC Number: