Uniform emulations of two different types of shuffle-exchange networks

Abstract

Uniform network emulations are a method t o obtain efficient and structure preserving simulations of large networks on smaller networks. There are two slightly different types of graphs, both realizing Stone's concept of a shuffle-exchange network: the (classical) shuffle exchange graph and the 4-pin shuffle. We analyze the uniform emulations both types of graphs allow, give a complete characterisation of the possible uniform emulations of the (classical) shuffle-exchange graph with 2n nodes on itself and on the 4-pin shuffle with 2n-1 nodes, and show that the 4-pin shuffle allows uniform emulations in instances where the (classical) shuffle-exchange graph does not.