Reliable Embedding of Paths in M(o)bius Cubes with Faulty Nodes

摘要：

The M(o)bius cube is an important variation of the hypercube.It possesses many desirable properties for interconnection networks. In this paper, we study reliable embedding of paths in Mobius cubes with faulty nodes. Let 0-MQn(V, E) and 1-MQn(V, E) denote the 0-type and 1-type n-dimensional M(o)bius cubes, respectively. We prove that a path of length l can be embedded between any two distinct nodes with dilation 1 for any faulty set F (∩) V(j-MQn) with |F|≤ n-3 and any integer l with2n-1-1≤l ≤|V(j-MQn-F)|-l for any integers n≥ 3 and j(E)0, 1.This result is optimal in the sense that the embedding has the mallest dilation 1.

作者: Jianxi Fan Jiwen Yang Xiaohua Jia Lei Zhao

作者单位: School of Computer Science and Technology Soochow University,Suzhou 215006,China Department of Computer Science City University of Hong Kong,Tat Chee Avenue,Hong Kong

会议类型: 国际会议

会议名称: The Inaugural Symposium on Parallel Algorithms, Architectures and Programming(并行算法、结构和编程国际研讨会)

会议地点: 广州

会议语种:英文

页码: 53-65

在线出版日期: 2008-09-16（万方平台首次上网日期，不代表论文的发表时间）