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
J. Bruck, Robert E. Cypher, et al.
FTCS 1993
Alok Aggarwal, R.J. Anderson, et al.
SIAM Journal on Computing
J. Bruck, Luc de Coster, et al.
IPDPS 1994