Name
Title | ||
|---|---|---|
Efficient algorithms for checking the equivalence of multistage interconnection networks |
Abstract | ||
|---|---|---|
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(N4 log N)). Finally, we determine the number of different equivalence classes of (2 log N - 1) stage MINs and we characterize each of them. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.jpdc.2003.09.003 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
layered cross,n log,stage mins,topologically equivalent mins,efficient algorithm,multistage interconnection networks,n4 log,different equivalence class,topological equivalence problem,equivalence class,baseline equivalent mins,topological equivalence,n stage,log n stage,multistage interconnection network | Binary logarithm,Discrete mathematics,Combinatorics,Algorithm,Multistage interconnection networks,Topological equivalence,Equivalence (measure theory),Topological conjugacy,Concatenation,Equivalence class,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
64 | 1 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
3 | 0.43 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tiziana Calamoneri | 1 | 511 | 46.80 |
| Annalisa Massini | 2 | 137 | 15.53 |