On finding maximal subcubes in residual hypercubes

It is useful in situations where some of the nodes of the hypercube multiprocessor are faulty or otherwise busy and unavailable for the application at hand, and one is required to utilize the available (residual) portion of the multiprocessor to the best possible extent. The authors resent an efficient algorithm for determining a subcube of maximum dimension in the residual hypercube when all the available nodes are listed explicitly. The algorithm takes O( nm²) time on a n-dimensional residual hypercube with m available nodes, as compared with the O(m2 ^m) time bound of the algorithm of Ozguner and Aykanat. The authors show an O(n)-time parallel version of this algorithm. Finally, they show that when the available nodes are described by subcube descriptors rather than by an explicit list of all available nodes, the problem of finding a maximum-dimension subcube becomes co-NP-hard