Conference paper
Fault tolerant graphs, perfect hash functions and disjoint paths
Miklos Ajtai, N. Alon, et al.
FOCS 1992
We consider the problem of broadcasting on an n-dimensional hypercube with worm-hole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log2(n + 1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.
Miklos Ajtai, N. Alon, et al.
FOCS 1992
Amotz Bar-Noy, J. Bruck, et al.
SPDP 1993
Alok Aggarwal, R.J. Anderson, et al.
STOC 1989
Alok Aggarwal, R.J. Anderson, et al.
SIAM Journal on Computing