On a generalization of triangulated graphs for domains decomposition of CSPs

Abstract

In [Jegou, 1993 ], a decomposition method has been introduced for improving search efficiency in the area of Constraint Satisfaction Problems. This method is based on properties of micro-structure of CSPs related to properties of triangulated graphs. This decomposition allows to transform an instance of CSP in a collection of sub-problems easier to solve, and then gives a natural and efficient way for a parallel implementation [Habbas eta!., 2000]. In this paper, we present a generalization of this approach, which is based on a generalization of triangulated graphs. This generalization allows to define the level of decomposition which can be fixed by a graph parameter. The larger this parameter is, the more level of decomposition that is the number of sub-problems is. As a consequence, we can then define the level of decomposition, with respect to the nature of the parallel configuration used (the number of processors). First experiments reported here show that this extension increases significantly the advantage of the basic decomposition, already shown in [Habbas et a/.,2000].