Complete binary trees in folded and enhanced cubes. (English) Zbl 1054.68098
Summary: It is well known that the complete binary tree \(B_n\) \((n \geq 3)\) on \(2^n - 1\) vertices is not embeddable into the \(n\)-dimensional hypercube. In this article, we describe a recursive technique to embed \(B_n\) into the \(n\)-dimensional folded and enhanced cubes, if \(n\) satisfies certain necessary parity conditions.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | El-Amawy, IEEE Transact Parallel Distributed Syst 2 pp 31– (1991) |
| [2] | and Optimal ring embedding in hypercubes with faulty links, Proc. 22nd IEEE International Symposium on Fault-Tolerant Computing, 1992, pp. 178-184. |
| [3] | Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes, Morgan Kaufmann, San Mateo, CA, 1992. · Zbl 0743.68007 |
| [4] | and Fault tolerance of the cyclic buddy subcube location scheme in hypercubes, Proc. 6th IEEE Distributed Memory Computing Conference, 1991, pp. 34-41. |
| [5] | Monien, Comput 7 pp 257– (1990) |
| [6] | Parallel computing: Theory and practice, McGraw-Hill (International Edition), Singapore, 1994. |
| [7] | Tzeng, IEEE Transact Comput 40 pp 284– (1991) |
| [8] | Wang, Congressus Numerantium 134 pp 89– (1998) |
| [9] | Wang, IEEE Transact Comput 48 pp 1369– (1999) |
| [10] | Wang, J Parallel Distributed Comput 61 pp 545– (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
