A New Approach to the Rearrangeability of (2log N-1) Stage MINs

In this paper we present a twofold result. First we provide a new routing algorithm to realize any permutation on all $(2 \log N -1) stage MINs in the class of Benes equivalent networks. The time complexity is the same as the Looping algorithm, i.e. O(Nlog N), but the interest of the presented algorithm derives from that it is very general and it runs on every network in the class apart from its symmetry. Furthermore, it provides a constructive proof of rearrangeability for a wide class of networks, substituting all the different proofs presented in literature. Second, we prove the rearrangeability of a class of MINs whose rearrangeability was not known; for them we describe an O(Nlog N) time routing algorithm.

PS Files

Conference Version