Reconfiguring embedded task graphs in faulty hypercubes by automorphisms
Sing-Ban Tien, Cauligi S. Raghavendra, M.A. Sridhar · 2002
The authors develop graph-theoretical techniques using automorphisms to solve the problem of reconfiguring embedded task graphs in faulty hypercubes. Four cases are considered: single node or link failure, small number (or=5) of random node failures. For single node (link) failure, any arbitrary task graphs embedded in a hypercube can be remapped to another instance of that graph by simple bit-flip operations. It takes at most O(n) such operations in an n-dimensional hypercube. For a small number of faults (>