Efficient algorithms for checking the equivalence of multistage interconnection networks

In this paper we study the topological equivalence problem of multistage interconnection networks (MINs). We prove a new characterization of topologically equivalent MINs by means of a novel approach. Applying this characterization to log N stage MINs we completely describe the equivalence class which the Reverse Baseline belongs to. Most important, we apply the characterization to (2 log N - 1) stage MINs obtained as concatenation of two log N stage Reverse Baseline equivalent MINs: in this way, we deduce an O(N log N) time algorithm testing the equivalence of two such MINs. This result substantially improves the time complexity of the previously known algorithms (O(N-4 log N)). Finally, we determine the number of different equivalence classes of (2 log N - 1) stage MINs and we characterize each of them. (C) 2003 Elsevier Inc. All rights reserved.