EMBEDDING CUBE-CONNECTED CYCLES GRAPHS INTO FAULTY HYPERCUBES

We consider the problem of embedding a cube-connected cycles graph (CC C) into a hypercube with edge faults. Our main result is ah algorithm that, given a list of faulty edges, computes am embedding of the CCC t hat spans all of the nodes and avoids all of the faulty edges. The alg orithm has optimal running time and tolerates the maximum number of fa ults (in a worst-case setting). Because ascend-descend algorithms can be implemented efficiently on a CCC, this embedding enables the implem entation of ascend-descend algorithms, such as bitortic sort, on hyper cubes with edge faults. We also present a number of related results, i ncluding an algorithm for embedding a CCC into a hypercube with edge a nd node faults and an algorithm for embedding a spanning torus into a hypercube with edge faults.