36
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Minimal cycle cutset methods to solve constraint satisfaction problems

&
Pages 45-55 | Published online: 19 Mar 2007
 

Abstract

Dechter [2] has proposed a cycle cutset method to solve Constraint Satisfaction Problems (CSPs). This method arbitrarily selects a set of nodes as cycle cutset and hence may contain some nodes which does not lie on any cycle. This will increase the size of the cutset and hence the time complexity of the method. In this paper, two minimal cycle cutset methods are presented. These methods first obtain a minimal cycle cutset in the constraint graph and then solve the CSP. Two algorithms to obtain a minimal cycle cutset in a graph are also presented here. The modified methods are tested on several randomly generated CSPs. On a class of constraint graph, the modified methods almost always show better performance.

C.R. Categories:

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.