A d-move local permutation routing for the d-cube

AbstractOptimal packet routing algorithms for all binary d-cubes of dimension d ⩽ 7 are presented. The algorithms given are synchronous, offer distributed control, and assume d-port, multiaccepting communication. While the previous best known packet routing algorithm [3]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 the ternary 4-cube