Embedding long cycles in faulty k-ary 2-cubes

作者：Wang Shiying^*; Feng Kai; Zhang Shurong; Li Jing

来源：Applied Mathematics and Computation, 2012, 218(9): 5409-5413.

DOI：10.1016/j.amc.2011.11.026

• Fault-tolerance
• Cycle embeddings
• k-Ary 2-cubes
• Torus

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 (V-1, V-2) be the bipartition of the k-ary 2-cube, f(v1), f(v2) be the numbers of faulty vertices in V-1 and V-2, respectively, and f(e) be the number of faulty edges. In this paper, we prove that there exists a cycle of length k(2) - 2max{f(v1), f(v2)} in the k-ary 2-cube with 0 <= f(v1) + f(v2) + fe <= 2. This result is optimal with respect to the number of faults tolerated.

• 出版日期2012-1
• 单位山西大学