The incrementally extensible hypercube (IEH) graph is a generalization of binary
hypercube networks in that the number of nodes can be arbitrary in contrast to a
strict power of 2. In this paper, the authors present an efficient model to fulfill
the embedding of a full binary tree into a full IEH graph. As the model the authors
proposed, an algorithm is developed for the embedding with expansion 1, load 1,
congestion 2, and dilation 2. Moreover, the embedding algorithm can be also applied
into hypercubes with one faulty node.
Get full access to this article
View all access options for this article.
References
1.
Chaudhary, V.
, and
Aggarwal, J. K.
1990.
Generalized mapping of parallel algorithms onto parallel architectures
. Proc. Intl. Conf. Parallel Processing, pp.
137-141
.
2.
Johnsson, S. L.1987.
Communication efficient basic linear algebra computations on hypercube system
. J. Parallel Distrib. Comput.4 (2):
133-172
.
3.
Sur, S.
, and
Srimani, P. K.1995.
IEH graphs: A novel generalization of hypercube graphs
. Acta Informatica32:
597-609
.
4.
Sur, S.
, and
Srimani, P. K.
1994.
On the routing problem in fault IEH graphs
. In IEEE International Conference on Computers and Communications
(IPCCC-94), Scottsdale, AZ, pp.
90-96
.
5.
Tzeng, N.-F.
, and
Chen, H.-L.1998.
Fast compaction in hyper-cubes
. IEEE Trans. on Parallel and Distributed Systems9 (1):
50-55
.
6.
Wanger, A. S.1994.
Embedding the complete binary tree in the hypercube
. J. Parallel Distrib. Comput.20:
241-247
.
