zbMATH — the first resource for mathematics

Compact embedding of binary trees into hypercubes. (English) Zbl 1022.68594
From the introduction: The objective of this paper is to show how to embed a complete binary tree of height \(h\) into an incomplete hypercube of the smallest size and to look in a hypercube for an incomplete binary tree that is larger than the incomplete binary tree in a paper by N.-F. Tzeng, H. L. Chen and P.-J. Chuang [in: Proceedings of the 1990 International Conference on Parallel Processing, Vol. III (University Park, PA, 1990), Pennsylvania State Univ. Press, University Park, PA, 335-339 (1990)]. In Section 2, we describe some preliminaries for embedding. In Section 3, we prove that the complete binary tree can be embedded into an incomplete hypercube, then prove that the size of the incomplete hypercubes is the smallest. In Section 4, we look for an incomplete binary tree in a hypercube.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Katseff, H.P., Incomplete hypercubes, IEEE trans. comput., 37, 5, 604-608, (1988)
[2] Leighton, T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (), 406-408
[3] Leiss, E.L.; Reddy, H.N., Embedding complete binary trees into hypercubes, Inform. process. lett., 38, 197-199, (1991) · Zbl 0736.68064
[4] Nebesky, L., On cubes and dichotomic trees, Časopis P̌est. mat., 99, 164-167, (1974) · Zbl 0277.05101
[5] Tzeng, N.F.; Cheng, H.L.; Chuang, P.J., Embeddings in incomplete hypercubes, (), 335-339
[6] Wagner, A.S., Embedding the complete tree in the hypercube, J. parallel distributed comput., 20, 241-247, (1994) · Zbl 0805.68026
[7] Wu, A.Y., Embedding of tree networks into hypercubes, J. parallel distributed comput., 2, 238-249, (1985)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.