Complexity of Finding Uniform Emulations on Paths and Ring Networks

摘要

Uniform emulations are a method to obtain efficient, balanced simulations of large processor networks (guests) on smaller networks (hosts). Each uniform emulation has associated with it a constant c, called the computation factor, which is the size of the guest network divided by the size of the host network. In the paper it is proven that the problem to decide whether a given (strongly) connected graph (network) G can be uniformly emulated on a path or on a ring is NP-complete.