On optimal embeddings into incomplete hypercubes

摘要

The authors show the embeddings of various types ofn-node incomplete binary trees into n-node or (n+1)-node composite hypercubes with dilation of at most 2. They alsopresent lower bound proofs showing optimality of the dilation. Theycharacterize the class of incomplete binary trees which are subgraphs ofcomposite hypercubes. They present dilation 1 embedding of atwo-dimensional n-node mesh, where one dimension is a power oftwo, into its optimal n-node composite hypercube. When neitherdimension is a power of two, it is shown that a dilation 1 embedding isnot possible; thereby characterizing the class of two-dimensional meshesthat can be embedded into composite hypercubes with dilation 1. Alltwo-dimensional meshes are shown to be embeddable with dilation 1 ifexpansion greater than 1 but less than 2 is allowed. The authors alsoconsider two types of incomplete meshes and their embeddings into theiroptimal composite hypercubes