Reconfiguration of Spanning Trees in Faulty Hypercubes

Spanning trees have been used extensively in algorithms for hypercube communications and broadcasting. We present algorithms for reconnecting spanning trees and achieving communication among the nonfaulty nodes in the hypercube. The algorithms presented provide reconfiguration for the completely unbalanced spanning tree (CUST), balanced spanning tree (BST), and general spanning tree (GST) in hypercubes in the presence of single node failure. These algorithms can reconfigure around any single fault in 0(1) reconfiguration time with no dilation and will increase the congestion of a link by, at most, one. Simulation results for the algorithms under multiple faults also are presented.