UNIFORM D-EMULATIONS OF RINGS, WITH AN APPLICATION TO DISTRIBUTED VIRTUAL RING CONSTRUCTION

Emulations are a special kind of structure-preserving mappings between processor interconnection networks (graphs). In this paper, the notio n of emulation is generalized to the notion of d-emulation for any d g reater-than-or-equal-to 1. Several problems concerning the complexity of (uniform) d-emulations are studied. It is shown that the problem of deciding for arbitrary graphs H and G whether H can be uniformly d-em ulated on G is NP-complete for every fixed d is-an-element-of N. Also, it is shown that the problem of deciding for arbitrary rings R and pl anar graphs G whether R can be uniformly 2-emulated on G is NP-complet e. Further, a constructive proof is given of the fact that there alway s exists a uniform 3-emulation of a ring R on a graph G = (V, E) if \V (R)\ = k. \V(G)\ and k is-an-element-of N. This uniform 3-emulation of R on G is used as the basis for the Distributed Virtual Ring Construc tion Algorithm that only uses 2 Absolute value of E messages of O(1) b its and has time complexity less-than-or-equal-to 2(Absolute value of - 1). A traversal of the constructed virtual ring costs 2(Absolute val ue of V - 1) messages.