Congressus Numerantium, 126 (1997), pp.21-32.

Ömer Egecioglu and Maximilian Ibel

Asymptotic Hypercube Embeddings of Dynamic k-ary Trees

Abstract. Several algorithms are known for embedding dynamically growing trees onto hypercubes. In a dynamic k-ary tree each leaf node may spawn k new children at any given time. The embedding process must not reassign any tree node to another host node in the hypercube once it has been placed. Desirable properties of the embedding are low dilation and optimal load-balance. The existing algorithms are mainly directed toward optimizing the load balance for trees that are comparable in size to the host graph. It has been observed that in this case the naive approach of assigning newly spawned leaves to random neighbors in the hypercube host yields suboptimal results. We consider the asymptotic behavior of this naive placement algorithm. For symmetry reasons it is to be expected that the resulting process should lead to an asymptotically balanced load for dynamic k-ary trees. We give a formal proof of this based on the Matrix-tree theorem for graphs. The proof generalizes to arbitrary connected regular host graphs, such as tori networks.

omer@cs.ucsb.edu