 |
The multistage shuffle-exchange network is generalized, by replacing the perfect shuffle with an arbitrary permutation pi, in order to pass all permutations using a minimal number of stages. The universality of such a network is shown to be equivalent to the primitivity of a related regular digraph, thus showing that universality is decidable in polynomial time. Extensive computational results are presented that characterize all nonisomorphic minimal networks with up to 12 inputs. In addition, strong evidence is presented relating the minimal number of network stages needed to achieve universality to twice the index of primitivity of the corresponding digraph.
|
|
For the newest resources, visit Wolfram Repositories and Archives »
