A Graph Based Synthesis Algorithm for Solving CSPs

Wanlin Pang and Scott D. Goodwin

Many AI tasks can be formalized as constraint satisfaction problems (CSPs), which involve finding values for variables subject to a set of constraints. While solving a CSP is an NP-complete task in general, it is believed that efficiency can be significantly improved by exploiting the characteristics of the problem. In this paper, we present a solution synthesis algorithm called ω-CDGT which is an existing algorithm named CDGT augmented with a constraint representative graph called ω-graph. We show that the worst-case complexity of the ω-CDGT algorithm is better than other related algorithms.


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.