TY - GEN
T1 - Longest fault-free paths in hypercubes with both faulty nodes and edges
AU - Hsieh, Sun Yuan
AU - Kuo, Che Nan
AU - Huang, Hui Ling
PY - 2007
Y1 - 2007
N2 - The hypercube is one of the most versatile and efficient interconnection networks for parallel computation. Let Fv (respectively, F e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Qn. In this paper, we show that Qn - Fv - Fe contains a fault free path with length at least 2n - 2|Fv| - 1 (or 2n - 2|Fv| - 2) between two arbitrary vertices of odd (or even) distance if |Fv| + |Fe| ≤ n - 2, where n > 3. Since Qn is bipartite of equal-size partite sets, the path is longest in the worst case. Furthermore, since Qn is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.
AB - The hypercube is one of the most versatile and efficient interconnection networks for parallel computation. Let Fv (respectively, F e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Qn. In this paper, we show that Qn - Fv - Fe contains a fault free path with length at least 2n - 2|Fv| - 1 (or 2n - 2|Fv| - 2) between two arbitrary vertices of odd (or even) distance if |Fv| + |Fe| ≤ n - 2, where n > 3. Since Qn is bipartite of equal-size partite sets, the path is longest in the worst case. Furthermore, since Qn is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free path obtained are worst-case optimal.
UR - http://www.scopus.com/inward/record.url?scp=52249099509&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=52249099509&partnerID=8YFLogxK
U2 - 10.1109/fgcn.2007.163
DO - 10.1109/fgcn.2007.163
M3 - Conference contribution
AN - SCOPUS:52249099509
SN - 0769530486
SN - 9780769530482
T3 - Proceedings of Future Generation Communication and Networking, FGCN 2007
SP - 605
EP - 608
BT - Proceedings of Future Generation Communication and Networking, FGCN 2007
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2007 International Conference on Future Generation Communication and Networking, FGCN 2007
Y2 - 6 December 2007 through 8 December 2007
ER -