TIME LOWER BOUNDS FOR PERMUTATION ROUTING ON MULTI-DIMENSIONAL BUSED MESHES
STEVEN CHEUNG, Francis C. M. Lau · Parallel Processing Letters · 1993
We present time lower bounds for the permutation routing problem on three- and higher-dimensional n x…x n meshes with buses. We prove an (r–1)n/r lower bound for the general case of an r-dimensional bused mesh, r≥2, which is not as strong for low-dimensional as for higher-dimensional cases. We then use a different approach to construct a 0.705n lower bound for the three-dimensional case.