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

Sun Yuan Hsieh, Che Nan Kuo, Hui Ling Huang

研究成果: Conference contribution

摘要

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.

原文English
主出版物標題Proceedings of Future Generation Communication and Networking, FGCN 2007
發行者Institute of Electrical and Electronics Engineers Inc.
頁面605-608
頁數4
ISBN(列印)0769530486, 9780769530482
DOIs
出版狀態Published - 2007
事件2007 International Conference on Future Generation Communication and Networking, FGCN 2007 - Jeju Island, Korea, Republic of
持續時間: 2007 十二月 62007 十二月 8

出版系列

名字Proceedings of Future Generation Communication and Networking, FGCN 2007
2

Other

Other2007 International Conference on Future Generation Communication and Networking, FGCN 2007
國家Korea, Republic of
城市Jeju Island
期間07-12-0607-12-08

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Software
  • Electrical and Electronic Engineering

引用此