A Mathematical Abstraction of the Rearrangeability Conjecture for Shuffle-Exchange Networks

Shuffle-exchange network has received a great deal of attention as an interconnecting network for parallel computing. One unsolved problem is the minimum number of stages required by a shuffle-exchange network with 2 sup n inputs and outputs to be rearrangeable. It turns out that this problem was studied much earlier by Benes in his work on switching network. Benes also conjectured that 2n - 1 stages suffice for rearrangeability and published the conjecture in a more general setting in 1975. So far, the conjecture has been verified only for n