Advertisement
Published in:
2005 | OriginalPaper | Chapter
Embedding of Cycles in the Faulty Hypercube
Author : Sun-Yuan Hsieh
Published in: Advances in Computer Systems Architecture
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
f
v
(respectively,
f
e
) denote the number of faulty vertices (respectively, edges) in an
n
-dimensional hypercube. In this paper, we show that a fault-free cycle of length of at least 2
n
–2
f
v
can be embedded in an
n
-dimensional hypercube with
f
e
≤
n
– 2 and
f
v
+
f
e
≤ 2
n
– 4. Our result not only improves the previously best known result of Sengupta (1998) where
f
v
> 0 or
f
e
≤
n
– 2 and
f
v
+
f
e
≤
n
– 1 were assumed, but also extends the result of Fu (2003) where only the faulty vertices are considered.