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.
Description:
Due to copyright restrictions, the access to the publisher version (published version) of this article is only available via subscription. You may click URI (with DOI: 10.1007/s100920170005) and have access to the Publisher Version of this article through the publisher web site or online databases, if your Library or institution has subscription to the related journal or publication.