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

Meeting Name

3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997


Computer Science

Keywords and Phrases

Computational Complexity; Fast Algorithm; Hypercube; Hypercube Networks; Overlapping Subcubes; Subcube Recognition

Document Type

Article - Conference proceedings

Document Version

Final Version

File Type





© 1997 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Full Text Link