The complete subcube recognition problem is defined as, given a collection of available processors on an n-dimensional hypercube, locate a subcube of dimension k that consists entirely of available processors, if one exists. Despite many algorithms proposed so far on this subject, improving the time complexity of this problem remains a challenge. Efficiency limits that can be reached have not been exhausted yet. This paper proposes a novel algorithm to recognize all the overlapping subcubes available on an n-dimensional hypercube whose processors are partially allocated. Given P=2n, as the total number of processors in the hypercube, the new algorithm runs in O(n x 3n) or O(Plog23 log2P) time which is an improvement over previously proposed strategies, such as multiple-graycode, missing combination, maximal set of subcubes, and tree collapsing
F. Erçal and H. J. Burch, "A Fast Algorithm for Complete Subcube Recognition," Proceedings of the 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997, Institute of Electrical and Electronics Engineers (IEEE), Jan 1997.
The definitive version is available at https://doi.org/10.1109/ISPAN.1997.645059
3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997
Keywords and Phrases
Computational Complexity; Fast Algorithm; Hypercube; Hypercube Networks; Overlapping Subcubes; Subcube Recognition
Article - Conference proceedings
© 1997 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 Jan 1997