Title :
Cycle embedding in a faulty hypercube
Author_Institution :
Dept. of Electron. Eng., Nat. Lien-Ho Inst. of Technol., Taiwan
Abstract :
The hypercube is one of the most versatile and efficient interconnection networks yet discovered for parallel computation. We show that a fault-free cycle of length of at least 2n - 2f can be embedded in an n dimensional hypercube with f faulty nodes, where n ≥ 3 and 1 ≤ f ≤ 2n - 4. The best known results thus far can tolerate only n - 1 faulty nodes.
Keywords :
fault tolerant computing; graph theory; hypercube networks; cycle embedding; fault-free cycle; faulty hypercube; faulty nodes; interconnection networks; n dimensional hypercube; parallel computation; Computational modeling; Computer networks; Concurrent computing; Costs; Distributed computing; Electronic mail; Fault tolerance; Hypercubes; Intelligent networks; Multiprocessor interconnection networks;
Conference_Titel :
Parallel and Distributed Systems, 2002. Proceedings. Ninth International Conference on
Print_ISBN :
0-7695-1760-9
DOI :
10.1109/ICPADS.2002.1183370
