EFFICIENT BROADCAST ON HYPERCUBES WITH WORMHOLE AND E-CUBE ROUTINGS
Ching‐Tien Ho, Ming‐Yang Kao · Parallel Processing Letters · 1995
We consider the problem of broadcasting on an n-dimensional hypercube with wormhole 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/ log 2(n+1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.