Optimal ring embedding in hypercubes with faulty links

Abstract

The authors show that in an n-dimensional hypercube (Q/sub n/), up to n-2 links can fail before destroying all available Hamiltonian cycles. They present an efficient algorithm which identifies a characterization of a Hamiltonian cycle in Q/sub n/, with as many as n-2 faulty links, in O(n/sup 2/) time. Generating a fault-free Hamiltonian cycle from this characterization can be easily done in linear time. An important application of this work is in optimal simulation of ring-based multiprocessors or multicomputer systems by hypercubes. Compared with the existing fault-tolerant embeddings based on link-disjoint Hamiltonian cycles, the algorithm specifies such a cycle that tolerates twice as many faulty links.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>