Routing permutations on a graph

We study off‐line routing of permutations π in arbitrary connected graphs. By insisting that routings be congestion‐free, we can rephrase the problem as one of factoring π into a minimal length product of permutations that move messages a distance of at most one, or alternatively, as the problem of finding a shortest path from the identity permutation to π in a certain Cayley graph of the symmetric group on the nodes. For the complete k ‐partite graph K n,n ,…., n , every π can be routed in two steps. We investigate a method for finding minimal factorizations. It involves finding perfect matchings in certain bipartite graphs associated with π. For the n ‐dimensional hypercube Q n , the well‐known upper bound of 2 n − 1 for the number of steps in which all π′s can be routed (obtained via the Beneš network) is reduced to 2 n − 2. We prove some results about permutations of Q n that are close to the antipodal map. A number of examples on Q 3 and Q 4 illustrate our method and compare it with those used by others. © 1993 by John Wiley & Sons, Inc.