A graph theoretical approach to equivalence of multistage interconnection networks (Q1119597)

The authors consider multistage interconnection networks for designed communication in multiprocessor architecture. They have defined a graph model of multistage interconnection network which yields an easy characterization of baseline equivalent networks. Checking the conditions can be done formally using the networks definitions, or algorithmically in the more general case of directed graphs. As the algorithm consists mainly in covering the graph, its complexity is linear in the number of nodes. The characterization proves that the six classical multistage interconnection networks are topologically equivalent.