Longest fault-free paths in hypercubes with vertex faults |
| |
Authors: | Jung-Sheng Fu |
| |
Affiliation: | Department of Electronics Engineering, National United University, 1, Lien Da, Kung-Ching Li, Miaoli 36003, Taiwan, ROC |
| |
Abstract: | The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ? n − 2, the n-cube contains a fault-free path with length at least 2n − 2f − 1 (or 2n − 2f − 2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n − 1 faulty vertices. Hence, our result is optimal. |
| |
Keywords: | Bipartite graph Fault tolerant embedding Hypercube Interconnection network |
本文献已被 ScienceDirect 等数据库收录! |
|