A New Method for Solving Constraint Satisfaction Problems
Abstract
This paper deals with the combinatorial search problem of finding values for a set of variables subject to a set of constraints. This problem is referred to as a constraint satisfaction problem. We present an algorithm for finding all the solutions of a constraint satisfaction problem with worst case time bound 0(m*kf+1) and space bound 0(n*kf+1), where n is the number of variables in the problem, m the number of constraints, k the cardinality of the domain of the variables, and f<n an integer depending only on a graph which is associated with the problem. It will be shown that for planar graphs and graphs of fixed genus this f is 0(n).
Cite
Text
Seidel. "A New Method for Solving Constraint Satisfaction Problems." International Joint Conference on Artificial Intelligence, 1981.Markdown
[Seidel. "A New Method for Solving Constraint Satisfaction Problems." International Joint Conference on Artificial Intelligence, 1981.](https://mlanthology.org/ijcai/1981/seidel1981ijcai-new/)BibTeX
@inproceedings{seidel1981ijcai-new,
title = {{A New Method for Solving Constraint Satisfaction Problems}},
author = {Seidel, Raimund},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1981},
pages = {338-342},
url = {https://mlanthology.org/ijcai/1981/seidel1981ijcai-new/}
}