d-Move Local Permutation Routing for the d-Cube
07 February 1997
Optimal packet routing algorithms for all binary d-cubes of dimension d = 7 are presented. The algorithms given synchronous, offer distributed control, and assume d-port, multiaccepting communication. While the previous best known packet routing algorithm [8] on the 7-cube takes 11 time-units, our algorithm has reduced the worst-case time complexity to the minimum possible of 7 units. We also give an optimal routing algorithm for a ternary 4-cube.