Routing Permutations on a 2D Grid with One-Way Edges
Petrişor Panaite · Parallel Processing Letters · 1997
We deal with the permutation routing problem on the m × n grid with one-register vertices and one-way edges. We give a routing algrithm of O(m + n) steps which is local, that is, the routing decision of every vertex depends on the states of vertices O(1) apart. Previous work investigated either local routings on two-way edges or non local routings on one-way edges.