Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (4): 62-65.DOI: 10.3778/j.issn.1002-8331.1806-0093

Previous Articles     Next Articles

Diagnosability of Unidirectional k-Ary n-Cubes Under PMC Model

ZHANG Wenli, LIN Shangwei, LI Yihai, GUO Huiling   

  1. School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China
  • Online:2019-02-15 Published:2019-02-19



  1. 山西大学 数学科学学院,太原 030006

Abstract: The connectivity and diagnosability of graphs are two parameters that are closely related to the reliability of interconnection networks. The [g]-good-neighbor connectivity and [g]-good-neighbor diagnosability are more accurate indexes than the connectivity and diagnosability. The [k]-ary [n]-cube is one of the most common interconnection networks for multiprocessor systems, and the unidirectional [k]-ary [n]-cube is the [k]-ary [n]-cube with simplex unidirectional links. This paper shows that the [1]-good-neighbor connectivity, the diagnosability and the [1]-good-neighbor diagnosability of the unidirectional [k]-ary [n]-cube under the PMC model are [k(n-1),] [n] and [kn-1,] respectively.

Key words: directed network, unidirectional [k]-ary [n]-cube, diagnosability, connectivity, PMC model

摘要: 图的连通度和诊断度是与互连网络的可靠性密切相关的两个参数,而[g]好邻连通度和[g]好邻诊断度是比连通度和诊断度更精确的指标。[k]元[n]立方体是多处理机系统的最常用网络之一,而单向[k]元[n]立方体是指具有单向边的[k]元[n]立方体。证明了当[k≥3,n≥3]时,单向[k]元[n]立方体在PMC模型下的[1]好邻连通度是[k(n-1)],诊断度是[n]且[1]好邻诊断度是[kn-1]。

关键词: 有向网络, 单向[k]元[n]立方体, 诊断度, 连通度, PMC模型