Binary Representations for General CSPs
Wanlin Pang, Scott D. Goodwin · 2001
It is well known that a non-binary constraint satisfaction problem (CSP) can be transformed into an equivalent binary CSP using the dual graph transformation. It is also known that the dual graph transformation is impractical in some cases where the CSP has a large number of constraints and/or the constraints have a larger number of satisfying tuples. However, little work has been done on improving transformation methods. In this paper, we introduce a constraint representative graph called !-graph and present a new transformation methods based on the !-graph. We show that the !-graph based transformation is a generalization of the dual graph transformation and it overcomes certain weaknesses of the dual graph transformation in many cases. Content Areas: constraint satisfaction Introduction A non-binary constraint satisfaction problem (CSP) can either be solved directly or transformed into a binary one and then solved by using binary CSP techniques. There have been dire...