An Improved Characterization of 1-Step Recoverable Embeddings: Rings in Hypercubes
This document has been relocated to http://scholarsmine.mst.edu/comsci_facwork/177
There were 2 downloads as of 27 Jun 2016.
Abstract
An embedding is 1-step recoverable if any single fault occurs, the embedding can be reconfigured in one reconfiguration step to maintain the structure of the embedded graph. In this paper we present an efficient scheme to construct this type of 1-step recoverable ring embeddings in the hypercube. Our scheme will guarantee finding a 1-step recoverable embedding of a length-k (even) ring in a d-cube where 6 less than or equal to k less than or equal to (3/4)2/sup d/ and d greater than or equal to 3, provided such an embedding exists. Unlike previously proposed schemes, we solve the general problem of embedding rings of different lengths and the resulting embeddings are of smaller expansion than in previous proposals. A sufficient condition for the non-existence of 1-step recoverable embeddings of rings of length >(3/4)2d in d-cubes is also given
