Optimal fault-tolerant embedding of paths in twisted cubes

被引:53
作者
Fan, Jianxi
Lin, Xiaola
Pan, Yi
Jia, Xiaohua
机构
[1] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
[2] Sun Yat Sen Univ, Coll Informat Sci & Technol, Guangzhou, Peoples R China
[3] Georgia State Univ, Dept Comp Sci, Atlanta, GA 30303 USA
关键词
twisted cube; fault tolerant; path; embedding; dilation; parallel computing system;
D O I
10.1016/j.jpdc.2006.04.004
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let TQ(n)(V, E) denote the n-dimensional twisted cube. We prove that a path of length I can be embedded between any two distinct nodes with dilation 1 for any faulty set F subset of V(T Q(n)) boolean OR E(T Q(n)) with \F\ <= n - 3 and any integer l with 2(n-1) - 1 <= l <= \V (T Q(n) - F)\-1 (n >= 3). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l and faulty set size \F\ for a successful embedding are tight. That is, the result does not hold if l <= 2(n-1) - 2 or \F\ >= n - 2. We also extend the result on (n - 3) -Hamiltonian connectivity of T Q(n) in the literature. (C) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码:205 / 214
页数:10
相关论文
共 30 条
[1]   Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes [J].
Bae, MM ;
Bose, B .
IEEE TRANSACTIONS ON COMPUTERS, 2003, 52 (10) :1271-1284
[2]   The congestion of n-cube layout on a rectangular grid [J].
Bezrukov, SL ;
Chavez, JD ;
Harper, LH ;
Röttger, M ;
Schroeder, UP .
DISCRETE MATHEMATICS, 2000, 213 (1-3) :13-19
[3]   Topological properties of twisted cube [J].
Chang, CP ;
Wang, JN ;
Hsu, LH .
INFORMATION SCIENCES, 1999, 113 (1-2) :147-167
[4]  
Chaudhary V., 1990, INT C PARALLEL PROCE, V2, P137
[5]   Fast sorting algorithms on a linear array with a reconfigurable pipelined bus system [J].
Datta, A ;
Soundaralakshmi, S ;
Owens, R .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2002, 13 (03) :212-222
[6]   EMBEDDING OF CYCLES IN ARRANGEMENT GRAPHS [J].
DAY, K ;
TRIPATHI, A .
IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (08) :1002-1006
[7]  
DIETZFELBINGER M, 1997, P 29 ACM S THEOR COM, P373
[8]  
FAN J, IN PRESS IEEE T PARA
[9]   Optimal path embedding in crossed cubes [J].
Fan, JX ;
Lin, XL ;
Jia, XH .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (12) :1190-1200
[10]   The t/k-diagnosability of the BC graphs [J].
Fan, JX ;
Lin, XL .
IEEE TRANSACTIONS ON COMPUTERS, 2005, 54 (02) :176-184