OPTIMAL SUBCUBE EMBEDDABILITY IN HYPERCUBES WITH ADDITIONAL DIMENSIONS
Abstract
Subcube embeddability of the hypercube can be enhanced by introducing an additional dimension. A set of new dimensions, characterized by the Hamming distance between the pairs of nodes it connects, is introduced using a measure defined as the magnitude of a dimension. An enumeration of subcubes of various size is presented for a dimension parameterized by its magnitude. It is shown that the maximum number of subcubes for a Qn can only be attained when the magnitude of dimension is n-1 or n. It is further shown that the latter two dimensions can optimally increase the number of subcubes among all possible choices.
References
- IEEE Trans. on Computers 37, 867 (1988), DOI: 10.1109/12.2234. Crossref, ISI, Google Scholar
- IEEE Trans. on Computers 28, 907 (1979). ISI, Google Scholar
- Communication of the ACM 24, 300 (1981), DOI: 10.1145/358645.358660. Crossref, ISI, Google Scholar
M. S. Chen and K. G. Shin , Embedment of Interacting Task Modules into A Hypercube Multiprocessor, Proc. Second Hypercube Conf. pp. 121–129. Google Scholar- LNCS 4208, 61 (2006). Google Scholar
- Networks 47, 1 (2006), DOI: 10.1002/net.20089. Crossref, ISI, Google Scholar
- Parallel and Distributed Processing Symp. 19, 4200 (2007). Google Scholar
A. Al-Dhelaan and B. Bose , A New Strategy for Processor Allocation in an N-cube Multiprocessor, Proc. on Int'l Phoenix Conf. on Comp. and Comm. pp. 114–118. Google Scholar- IEEE Trans. on Computers 36, 1396 (1987). ISI, Google Scholar
J. Kim , C. R. Das and W. Lin , A Processor Allocation Scheme for Hypercube Computers, Proc. Int. Conf. on Parallel Processing pp. II-231–238. Google Scholar- IEEE Trans. On Computers 31, 443 (1982). ISI, Google Scholar
- IEEE Trans. On Computers 37, 472 (1988), DOI: 10.1109/12.2194. Crossref, ISI, Google Scholar
S. Latifi and A. El-Amawy , On Folded Hypercubes, Int'l Conf. on Parallel ProcessingI pp. I-180–I-187. Google Scholar- IEEE Trans. On Computers 38, 1425 (1988), DOI: 10.1109/12.35837. Crossref, ISI, Google Scholar
- IEEE Trans. on Reliability 39, 361 (1990), DOI: 10.1109/24.103019. Crossref, ISI, Google Scholar
J. Chen , I. A. Kanj and G. Wang , Hypercube Network Fault Tolerance: A Probabilistic Approach, Int'l Conf. on Parallel Processing pp. 65–72. Google Scholar


