Title :
On the Longest Fault-Free Paths in Hypercubes with More Faulty Nodes
Author :
Kueng, Tz-Liang ; Liang, Tyne ; Tan, Jimmy J M ; Hsu, Lih-Hsing
Author_Institution :
Dept. of Comput. Sci., Nat. Chiao Tung Univ., Hsinchu
Abstract :
Faults in a network may take various forms such as hardware/software errors, node/link faults, etc. In this paper, node-faults are addressed. Let F be a faulty set of f les 2n - 6 conditional node-faults in an injured n-cube Qn such that every node of Qn still has at least two fault - free neighbors. Then we show that Qn - F contains a path of length at least 2n - 2f - 1 (respectively, 2n - 2f - 2) between any two nodes of odd (respectively, even) distance. Since an n-cube is a bipartite graph, such kind of the fault- free path turns out to be the longest one in the case when all faulty nodes belong to the same partite set.
Keywords :
fault diagnosis; graph theory; hypercube networks; bipartite graph; fault-free path; faulty nodes; hardware errors; hypercubes; injured n-cube network; link fault; network fault; software errors; Bipartite graph; Computer errors; Computer networks; Computer science; Concurrent computing; Hardware; Hypercubes; Multiprocessor interconnection networks; Parallel architectures; Software algorithms; Conditional fault; Hypercube; Interconnection network; Linear array; Path embedding;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 2008. I-SPAN 2008. International Symposium on
Conference_Location :
Sydney, NSW
Print_ISBN :
978-0-7695-3125-0
DOI :
10.1109/I-SPAN.2008.29
