A Benes-like theorem for the shuffle-exchange graph
Eric J. Schwabe · IEEE Transactions on Computers · 1992
One of the first theorems on permutation routing, proved by V.E. Benes (1965), shows that give a set of source-destination pairs in an N-node butterfly network with at most a constant number of sources or destinations in each column of the butterfly, there exists a set of paths of lengths O(log N) connecting each pair such that the total congestion is constant. An analogous theorem yielding constant-congestion paths for off-line routing in the shuffle-exchange graph is proved here. The necklaces of the shuffle-exchange graph play the same structural role as the columns of the butterfly in the Benes theorem.>