Designing and Reconfiguring Fault-Tolerant Hypercubes
Abdel Aziz Farrag, Shituo Lou · 2006
Several interconnection networks (such as meshes and hypercubes) can be modeled as circulant graphs. As a result, methods previously developed for constructing fault-tolerant solutions of circulant graphs can also be applied to these networks. Among these methods, the one based on the idea of "offsets partitioning" is the most efficient (for circulant graphs). We review this method in this paper, and extend its applications to hypercubes. Moreover, we develop new algorithms to reconfigure circulant graphs and hypercubes. Our results show that the fault-tolerant solutions obtained, and the reconfiguration algorithms developed are efficient.