| 摘要: |
| 互连网络的容错能力是并行计算中的一个关键问题，而d进制n维方（超方的一般形式）在计算机的互连网络中已得到广泛的应用。本文考虑有节点故障的d进制n维方的容错性。F是d进制n维方Qn（d） 中的错误点集（n≥3）， 且|F|≤n-2，证明了Qn（d）的每个无故障的边和无故障的点存在于长从4到dn-2|F|的无故障偶圈中。而且，当d是奇数时，Qn（d）的每个无故障的边和无故障的点存在于长为dn-2|F|的无故障圈中。 |
| 关键词: 圈嵌入 超方 故障容错 互联网络 d进制 |
| DOI：10.13656/j.cnki.gxkx.20211109.002 |
| 投稿时间：2021-04-15 |
| 基金项目:国家自然科学基金项目（10771225）资助。 |
|
| Cycles Embedding in d-Ary n-Dimensional Cube With Node Failures |
|
LI Zhaoxiang
|
| (College of Science, Minzu University of China,Beijing,100081,China) |
| Abstract: |
| The d-ary n-dimensional cube (the general form of hypercube) has been widely used as the interconnection network in parallel computers.The fault-tolerant capacity of an interconnection network is a critical issue in parallel computing.In this article, we consider the fault-tolerant capacity of the d-ary n-dimensional cube.Let F be a set of faulty vertices in Qn(d) (n≥3) with |F|≤n-2, we prove that every fault-free edge and fault-free vertex (node) of Qn(d) lies on a fault-free cycle of every even length from 4 to dn-2|F|.Moreover, if d is an odd number, every fault-free edge and fault-free vertex (node) of Qn(d) lies on a fault-free cycle of length dn-2|F|. |
| Key words: cycle embedding hypercube fault-tolerant interconnection network d-ary |
