Rearrangeability of (2 log n N− 1)-stage networks employing a uniform connection pattern

Abstract

In this paper, we study the rearrangeablity of multistage networks. Although the necessity of (2 lgN −1)1 stages for rearrangeability of a shuffle-exchange network has been known, the sufficiency of (2 lgN −1) stages has never been proved. The best known upper bound for its rearrangeability is (3 lgN−4).We prove that (2 logn N−1) stages are sufficient for the rearrangeability of a multistage network with (n×n)-switches employing a uniform interconnection pattern. This, in particular, implies the sufficiency of (2 lgN−1) stages for the rearrangeability of a shuffle-exchange network.