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 -