Premium
Routing permutations on a graph
Author(s) -
Ramras Mark
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230420
Subject(s) - combinatorics , hypercube , mathematics , antipodal point , bipartite graph , cayley graph , permutation (music) , discrete mathematics , graph , physics , geometry , acoustics
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.