ROUTING PERMUTATIONS ON GRAPHS VIA FACTORS

We deal with the permutation routing problem on graphs modeling interc onnection networks. In our model, called routing via factors, at each routing step, the communication pattern is a directed 1-factor in a sy mmetric digraph. This acids a new feature, that of continuous packet m ovement, to preciously studied routing types, where the routing of a p ermutation is reduced to a sequence of permutations from a given class . We especially focus on bipartite graphs and we give sufficient condi tions for a graph to be rearrangeable in our model, We propose a gener al technic for routing via. factors that we apply to the 2D mesh and t he hypercube, (C) 1998 Academic Press.