Abstract
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
Recommended Citation
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
Meeting Name
3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997
Department(s)
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
text
Language(s)
English
Rights
© 1997 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Jan 1997
