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.
Published Date: May 2001
Registration: ISBN 978-1-57735-133-7
Copyright: Published by The AAAI Press, Menlo Park, California.