A general technique to establish the asymptotic conditional diagnosability of interconnection networks
A general technique to establish the asymptotic conditional diagnosability of interconnection networks
复制标题
DOI：
10.1016/j.tcs.2012.05.015
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
I. A. Stewart
中科院分区：
文献类型：
--
作者：
I. A. Stewart
我们开发了一个通用的和证明广泛适用的技术，用于确定并行计算中普遍存在的比较诊断模型下的互连网络的渐近条件可诊断性。我们应用我们的技术复制（但扩展）现有的结果，超立方体和k元n-立方体，然后再获得新的结果，折叠超立方体，煎饼图和增强立方体。特别地，我们证明了：折叠超立方体{Pn}的渐近条件可诊断性是3 n −2，煎饼图{Pn}是3 n −7，增广立方体{AQn}是6 n −17。我们证明了我们的技术是如何独立的互连网络G的结构特性的问题，基本上只依赖于在G中的长度为2的路径的邻域的最小大小，G中的任何两个不同的顶点的邻居的数量有共同的，和G中的任何顶点的最小程度。
We develop a general and demonstrably widely applicable technique for determining the asymptotic conditional diagnosability of interconnection networks prevalent within parallel computing under the comparison diagnosis model. We apply our technique to replicate (yet extend) existing results for hypercubes and k-ary n-cubes before going on to obtain new results as regards folded hypercubes, pancake graphs and augmented cubes. In particular, we show that the asymptotic conditional diagnosability of: folded hypercubes {FQn} is 3n−2, pancake graphs {Pn} is 3n−7, and augmented cubes {AQn} is 6n−17. We demonstrate how our technique is independent of structural properties of the interconnection network G in question and essentially only dependent upon the minimal size of the neighbourhood of a path of length 2 in G, the number of neighbours any two distinct vertices of G have in common, and the minimal degree of any vertex in G.