TY - GEN
T1 - Embedding of cycles in the faulty hypercube
AU - Hsieh, Sun Yuan
PY - 2005/12/1
Y1 - 2005/12/1
N2 - Let fv (respectively, fe) 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 2n -2f v can be embedded in an n-dimensional hypercube with fe ≤ n - 2 and fv + fe ≤ 2n - 4. Our result not only improves the previously best known result of Sengupta (1998) where fv > 0 or fe ≤ n - 2 and fv + fe ≤ n-1 were assumed, but also extends the result of Fu (2003) where only the faulty vertices are considered.
AB - Let fv (respectively, fe) 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 2n -2f v can be embedded in an n-dimensional hypercube with fe ≤ n - 2 and fv + fe ≤ 2n - 4. Our result not only improves the previously best known result of Sengupta (1998) where fv > 0 or fe ≤ n - 2 and fv + fe ≤ n-1 were assumed, but also extends the result of Fu (2003) where only the faulty vertices are considered.
UR - http://www.scopus.com/inward/record.url?scp=33646512384&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646512384&partnerID=8YFLogxK
U2 - 10.1007/11572961_19
DO - 10.1007/11572961_19
M3 - Conference contribution
AN - SCOPUS:33646512384
SN - 3540296433
SN - 9783540296430
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 229
EP - 235
BT - Advances in Computer Systems Architecture - 10th Asia-Pacific Conference, ACSAC 2005, Proceedings
T2 - 10th Asia-Pacific Conference on Advances in Computer Systems Architecture, ACSAC 2005
Y2 - 24 October 2005 through 26 October 2005
ER -