Asymptotically optimal probabilistic embedding algorithms for supporting tree structured computations in hypercubes
Keqin Li, John E. Dorband · 1999
We show two asymptotically optimal probabilistic tree embedding algorithms in hypercubes with constant dilation. These algorithms are slight extension of the random walk algorithm. The first algorithm allows a tree node to have a stay option during each step of a random walk. The second algorithm permits varying length of random walks. Numerical data are given to demonstrate performance improvement.