Fault-tolerance and reconfiguration of circulant graphs and hypercubes
Abdel Aziz Farrag, Shituo Lou, Yao Qi · Spring Simulation Multiconference · 2008
Several interconnection networks (such as rings, 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.