Uniform d‐emulations of rings, with an application to distributed virtual ring construction
Erwin M. Bakker, Jan Van Leeuwen · Networks · 1993
Abstract Emulations are a special kind of structure‐preserving mappings between processor interconnection networks (graphs). In this paper, the notion of emulation is generalized to the notion of d‐emulation for any d ≧ 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‐emulated on G is NP‐complete for every fixed d ϵ N. Also, it is shown that the problem of deciding for arbitrary rings R and planar graphs G whether R can be uniformly 2‐emulated on G is NP‐complete. Further, a constructive proof is given of the fact that there always exists a uniform 3‐emulation of a ring R on a graph G = (V, E) if |VRy| = k. |VG| and k ϵ N. This uniform 3‐emulation of R on G is used as the basis for the Distributed Virtual Ring Construction Algorithm that only uses 2|E| messages of O(1) bits and has time complexity ≦ 2(|V| − 1). A traversal of the constructed virtual ring costs 2(|V| − 1) messages. © 1993 John Wiley & Sons, Inc.