- Fast algorithms for bit-serial routing on a
hypercube. W. A. Aiello, F. T. Leighton, B. M. Maggs, and M.
Newman, Mathematical Systems Theory, Vol. 24, 1991, pp. 253-271.
- This paper presents a randomized algorithm for routing any
permutation of N (log N)-bit messages on an N-node hypercube in O(log
N) bit steps. Previous algorithms required at least Omega(log^2 N)
bit steps. The algorithm is adaptive, and we show that any O(log
N)-bit-step algorithm must be adaptive by generalizing the
Borodin-Hopcroft lower bound on oblivous routing. In particular, we
show that any randomized oblivious algorithm on a
polylogarithmic-degree network requires at least Omega(log^2 N/loglog N)
bit steps, with high probability, for almost all permutations.
- Back to other
- Back to my home page