Optimal Mapping of Neighbourhood-Constrained Systems

. The problem of finding the minimum topology of multiprocessing substrates supporting parallel execution of any given neighbourhood -constrained system is proposed and possible optimal strategies are investigated based on the relationship between Barbosa's scheduling by edge reversal - SER - distributed algorithm and the minimum clique covering problem. It is shown that from any given clique covering of length on a graph G, it is possible to obtain a SER trailer dynamics in G's complement that cover G upon evolutions. It also shown that, conversely, from any given SER dynamics on G in which all of its nodes operate at least once upon steps, a clique covering of length at most is defined on G's complement. In addition, a conjecture correlating the length of any minimum clique covering and optimal concurrency in SER- driven systems is stablished. 1 Introduction Scheduling by edge reversal - SER - is a powerful parallel and distributed graphbased algorithm developed [BaGa89] [Ba93]..