Longest fault-free paths in hypercubes with both faulty nodes and edges

Sun Yuan Hsieh, Che Nan Kuo, Hui Ling Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of Future Generation Communication and Networking, FGCN 2007
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages605-608
Number of pages4
ISBN (Print)0769530486, 9780769530482
DOIs
Publication statusPublished - 2007
Event2007 International Conference on Future Generation Communication and Networking, FGCN 2007 - Jeju Island, Korea, Republic of
Duration: 2007 Dec 62007 Dec 8

Publication series

NameProceedings of Future Generation Communication and Networking, FGCN 2007
Volume2

Other

Other2007 International Conference on Future Generation Communication and Networking, FGCN 2007
CountryKorea, Republic of
CityJeju Island
Period07-12-0607-12-08

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Software
  • Electrical and Electronic Engineering

Cite this