zbMATH — the first resource for mathematics

Dense sets and embedding binary trees into hypercubes. (English) Zbl 1111.05023
Summary: The purpose of this paper is to describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whose members allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
68M07 Mathematical problems of computer architecture
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] S. Bezrukov, B. Monien, W. Unger, G. Wechsung, Embedding caterpillars into the hypercube, Technical Report, University of Paderborn, 1995. · Zbl 0906.05019
[2] S. N. Bhatt, I. C. Ipsen, How to embed trees in hypercubes, Technical Report YALEU/DCS/RR-443, Yale University, 1985.
[3] Caha, R.; Koubek, V., Optimal embeddings of odd ladders into a hypercube, Discrete appl. math., 116, 73-102, (2002) · Zbl 1005.05016
[4] Caha, R.; Koubek, V., Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, J. graph theory, 51, 137-169, (2005) · Zbl 1084.05041
[5] Dvořák, T.; Havel, I.; Laborde, J.-M.; Liebl, P., Generalized hypercubes and graph embedding with dilation, Rostock. math. kolloq., 39, 13-20, (1990) · Zbl 0719.05036
[6] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[7] Harary, F.; Hayes, J.P.; Wu, H.-J., A survey of the theory of hypercube graphs, Comput. math. appl., 15, 277-289, (1988) · Zbl 0645.05061
[8] Harper, L.H., Optimal assignment of numbers to vertices, J. soc. indust. appl. math., 12, 131-135, (1964) · Zbl 0222.94004
[9] Heun, V.; Mayr, E.W., A new efficient algorithm for embedding arbitrary binary tree into its optimal hypercube, J. algorithms, 20, 375-399, (1996) · Zbl 0844.68044
[10] Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (1992), Morgan Kaufmann San Mateo, CA · Zbl 0743.68007
[11] Wagner, A.; Corneil, D.G., Embedding trees in a hypercube is NP-complete, SIAM J. comput., 7, 570-590, (1990) · Zbl 0698.68054
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.