Applying scheduling by edge reversal to constraint partitioning
Marluce Rodrigues Pereira, Patrícia Kayser Vargas Mangan, Felipe M. G. França, Maria Clicia Castro, Inês Dutra · 2004
Scheduling by edge reversal (SER) is a fully distributed scheduling mechanism based on the manipulation of acyclic orientations of a graph. This work uses SER to perform constraint partitioning of constraint satisfaction problems (CSP). In order to apply the SER mechanism, the graph representing the constraints must receive an acyclic orientation. Since obtaining an optimal acyclic orientation is an NP-hard problem, we study three nondeterministic strategies known in the literature: Alg-Neigh, Alg-Edges, and Alg-Colour. We implemented the three algorithms and the SER scheduling mechanism, applying them to the CSP constraint networks generated from 3 applications. Our results show that SER has a great potential to perform a good partitioning of the constraint graphs.