The classification of coverings of processor networks

Uniform emulations are known in the theory of parallel computing as a class of balanced, structure preserving simulations of large (processor-) networks on smaller (processor-) networks, possibly of the same type. The notion of a covering of one graph by another graph, derived from combinatorial topology, is strongly related to the notion of uniform emulation: every covering of a connected, undirected graph is a uniform emulation. A classification of the coverings of large networks on smaller networks of the same type is given for the following network types: the ring, the grid, the cube, the cube connected cycles, the tree network, and the complete network. A version of the notion of covering for directed graphs is introduced, and the directed coverings of the 4-pin shuffle and the shuffle-exchange networks are completely classified. The problem of deciding whether there is a covering of a given graph G = (V_G, E_G) on a given graph H = (V_H, E_H) is shown to be at least as hard as GRAPH ISOMORPHISM, even if |V_G|/|V_H| is fixed to a constant c ε{lunate} N⁺.