This paper considers a class of combined (2n - 1)-stage N x N interconnection networks composed of two n(= log(2)N)-stage omega-equivalent networks M(n) and M'(n). The two networks are concatenated with the last stage of M'(n) overlapped with the first stage of M(n), forming a combined (2n - 1) stage network. Though both Benes network and (2n - 1)-stage shuffle-exchange network belong to this class, the former one is a rearrangeable network, whereas the rearrangeability of the latter one is still an open problem. So far, there is no algorithm, in general, that may determine whether a given (2n - 1)-stage combined network is rearrangeable or not. In this paper, a sufficient condition for rearrangeability of a combined (2n - 1)-stage network has been formulated. An algorithm with time complexity O(Nn) is presented to check it. If it is satisfied, a uniform routing algorithm with time complexity O(Nn) is developed for the combined network. Finally, a novel technique is presented for concatenating two omega-equivalent networks, so that the rearrangeability of the combined network is guaranteed, and hence the basic difference between the topologies of a Benes network and a (2n - 1)-stage shuffle-exchange network has been pointed out. (c) 2004 Elsevier B.V. All rights reserved.
