๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Incomplete Hypercubes: Embeddings of Tree-Related Networks

โœ Scribed by S. Ohring; S.K. Das

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
911 KB
Volume
26
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

We consider the incomplete hypercubes, a generalization of the binary hypercube networks in the sense that the number of nodes can be arbitrary as opposed to a strict power of 2 . The capability of the incomplete hypercubes to execute parallel programs is studied here using graph embedding techniques. We show optimal (or nearly optimal) embeddings of various guest networks such as X-trees, full-ringed binary trees, tree machines, mesh of trees, and pyramids into the optimum-sized incomplete hypercube host. 1995 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Embedding Hypercubes and Related Network
Embedding Hypercubes and Related Networks into Mesh-Connected Processor Arrays
โœ F. Annexstein ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 736 KB

In this paper we study the problem of how computations programmed for hypercubes, and their bounded-degree relatives, the shuffle-exchange and cube-connected-cycles, can be efficiently emulated by mesh-connected arrays of processing elements. The emulations we present are implemented via graph embed

Efficient Dynamic Embeddings of Binary T
Efficient Dynamic Embeddings of Binary Trees into Hypercubes
โœ Volker Heun; Ernst W. Mayr ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 255 KB

In this paper, a deterministic algorithm for dynamically embedding binary trees into hypercubes is presented. Because of a known lower bound, any such algorithm must use either randomization or migration, i.e., remapping of tree vertices, to obtain an embedding of trees into hypercubes with small di