带有条件故障边的k元2方体的圈嵌入

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (5): 32-34.

带有条件故障边的k元2方体的圈嵌入

冯凯1，王世英2

1.山西大学计算机与信息技术学院，太原 030006
2.山西大学数学科学学院，太原 030006

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-11 发布日期:2012-02-11

Embedding cycles in k-ary 2-cubes with conditional edge faults

FENG Kai1, WANG Shiying2

1.School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China
2.School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-02-11 Published:2012-02-11

摘要/Abstract

摘要： [k]元[n]方体已经成为分布式储存并行系统最常用的网络拓扑结构。研究带有条件故障边的[k]元2方体的圈嵌入问题，证明了在[k≥4]为偶整数的[k]元2方体中，若其故障边数不超过3且每个顶点至少与两条非故障边相关联，那么该[k]元2方体存在长度在4到[k2]间的任意偶长的无故障圈。

关键词: k元2方体, 圈嵌入, 条件故障

Abstract: The k-ary n-cube has been the most commonly used interconnection topology for distributed-memory parallel systems. This paper considers the cycle embedding problem in k-ary 2-cubes with conditional edge faults and shows that there exists a cycle of every even length from 4 to[k2]in a k-ary 2-cube with at most 3 edge faults in which each vertex is incident with at least two healthy edges for even[k≥4].

Key words: k-ary 2-cubes, embedding cycles, conditional faults

冯凯1，王世英2. 带有条件故障边的k元2方体的圈嵌入[J]. 计算机工程与应用, 2012, 48(5): 32-34.

FENG Kai1, WANG Shiying2. Embedding cycles in k-ary 2-cubes with conditional edge faults[J]. Computer Engineering and Applications, 2012, 48(5): 32-34.