Fault-Tolerance and Reconfiguration of Circulant Graphs and Hypercubes

摘要

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.