EMBEDDING K-ARY COMPLETE TREES INTO HYPERCUBES

In this paper, dilated embedding and precise embedding of K-ary comple te trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of he ight h, T(K)(h), into an (h - 1)[log K] + [log (K + 2)]-dimensional hy percune with dilation Max{2, phi(K), phi(K + 2)}. phi(x) = min{lambda: SIGMA(i=0)lambda C(d)i greater-than-or-equal-to x and d = [log x]}. I t is clear that [([log x] + 1)/2] less-than-or-equal-to phi(x) less-th an-or-equal-to [log x], for x greater-than-or-equal-to 3.) For precise embedding, we show a (K - 1)h + 1-dimensional hypercube is large enou gh to contain T(K)(h) as its subgraph, K greater-than-or-equal-to 3. ( C) 1995 Academic Press, Inc.