Embedding long cycles in faulty k-ary 2-cubes |
| |
| Authors: | Shiying Wang Kai FengShurong Zhang Jing Li |
| |
| Institution: | a School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, People’s Republic of China
b School of Computer and Information Technology, Shanxi University, Taiyuan, Shanxi 030006, People’s Republic of China |
| |
| Abstract: | The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. Given an even k ? 4, let (V1, V2) be the bipartition of the k-ary 2-cube, fv1, fv2 be the numbers of faulty vertices in V1 and V2, respectively, and fe be the number of faulty edges. In this paper, we prove that there exists a cycle of length k2 − 2max{fv1, fv2} in the k-ary 2-cube with 0 ? fv1 + fv2 + fe ? 2. This result is optimal with respect to the number of faults tolerated. |
| |
| Keywords: | Fault-tolerance Cycle embeddings k-Ary 2-cubes Torus |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
