Binary Representations for General CSPs

Wanlin Pang, National Research Council of Canada, Canada and Scott D. Goodwin, University of Regina, Canada

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 omega-graph and present a new transformation methods based on the omega-graph. We show that the omega-graph based transformation is a generalization of the dual graph transformation and it overcomes certain weaknesses of the dual graph transformation in many cases.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.