Ring Embedding in an Injured Hypercube

We consider the problem of embedding a ring in a hypercube that contains possible faulty nodes. Existing algorithms allow the number of faulty nodes to be at most 2n-Theta(sqrt {nlogn}), where n is the dimension of the hypercube. We propose an embedding scheme that can tolerate up to Theta(2^{n/2}) faulty nodes, largely increasing the number of tolerable faulty nodes in a ring embedding.