Diagnosability of n-Dimensional Hypercubes and Folded Hypercubes with Missing Edges under the MM* Model
畅畅 樊 · Advances in Applied Mathematics · 2021
一个多重处理器系统的诊断度是测量互连网络错误容忍度的一个重要研究参数。n维折叠超立方体FQn是由n维超立方体Qn添加2n-1条边得到。在这篇文章中，我们首先研究了Qn在MM*模型下的诊断度，证明了Qn即使存在n-2条遗失边仍具有强局部诊断性，并且证明了n-2是最优值。然后，我们研究了FQn在MM*模型下的诊断度，证明了FQn即使存在n-1条遗失边仍具有强局部诊断性，并且证明了n-1是最优值。 Diagnosability of a multiprocessor system is an important research parameter to measure the fault tolerance of interconnection networks. The n-dimensional folded hypercube FQn is obtained by adding 2n-1 edges to the n-dimensional hypercube Qn. In this paper, we firstly study the diagnosability of Qn and prove that Qn has the strong local diagnosability property even if there exist n-2 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges. Then we study the diagnosability of FQn and prove that FQn has the strong local diagnosability property even if there exist n-1 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.