Transcript Fault-tolerant cycle embedding in the hypercube

Fault-tolerant cycle
embedding in the
hypercube
Jung-Sheng Fu
Department of Electronics Engineering, National Lien-Ho
Institute of Technology
Parallel Computing 29 (2003) 821-832
1
Previous results





The n-dimensional folded hypercube is (n-1)-link
Hamiltonian.
The n-dimensional star graph is (n-3)-link
Hamiltonian.
The arrangement graph An ,k is (k(n-k)-2)-link
Hamiltonian.
The WK-recursive network of degree d is (d-3)link Hamiltonian.
A modification of a d-ary undirected de Bruijn
graph is (d-1)-link Hamiltonian.
2
Previous results



The n-dimensional hypercube is (n-2)-link
Hamiltonian.
A fault-free cycle of length of at least 2n  2 f
can be embedded in an n-cube with f faulty
nodes, where 1<=f<=n-2.
An n-cube with fe<=n-4 faulty links and
fv<=n-1 faulty nodes such that fe+fv<=n-1, a
cycle of length of at least [(2^n)-2*fv] can be
obtained.
3
Abstract

A fault-free cycle of length of at least
(2^n)-2*f can be embedded in an n-cube
with f faulty nodes, where n>=3 and
1<=f<=2n-4.
4
Lemma 1


Let X and Y be two distinct nodes in an ncube and dH(X,Y)=d, where n>=1. There
are X-Y paths in the n-cube whose length
are d, d+2, d+4,…,c, where c=(2^n)-1 if
d is odd, and c=(2^n)-2 if d is even.
J.S. Fu, G.H. Chen, Hamiltonicity of the hierarchical cubic
network, Theory of Computing Systems 35(1)(2002)5979.
5
6
7


If f=0, then this lemma can be directly
obtained from Lemma 1.
If f=1
8
9
10


Case 1 f0=k-1, f1=1
Case 1.1
11
Case 1.2 All nodes in *0 (except X) adjacent to Y are faulty.
12



Case 1.3 Besides Y, at least one other healthy node
in *0 is adjacent to X.
Case 2. 2<=f0<=k-2
Case 3. f0=1, f1=k-1
13

Case 1. f0=2k-3, f1=1
14

Case 2. k<=f0<=2k-4, 1<=f1<=k-2
15

Case 3. f0=k-1, 1<=f1<=k-1
When f1<=k-2, the discussion
is the same as in Case 2.
Assume that f1=k-1. By
assumption, there exists a
fault-free cycle C of length of
at least [(2^k)-2*f0] in *0.
In addition, by Lemma 6, there
exists a fault-free U(k+1) ---V(k+1) path of length of at
least [(2^k)-2*f1-1] in *1.
16
Discussion and conclusion


It is not easy to prove that a fault-free
cycle of length of at least (2^n)-2*f
cannot be embedded in an n-cube with f
faulty nodes, where n>=5 and f>=2n-3.
This paper reveals that a bipartite graph
may tolerate faulty nodes more than its
degree without affecting the embedding
results.
17
18
Discussion and conclusion

To embed fault-free cycles in the star
graph, the butterfly graph, and the other
bipartite graph with more faulty nodes
tolerable is one of the further projects.
19