A New Method for Solving Constraint Satisfaction Problems
Proceedings of the Seventh International Joint Conference on Artificial Intelligence. INFERENCE and REASONING. Pages 338-341.
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 O(m*kf+l) and space bound O(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 O( / nJ.
@inproceedings{ijcai1981p66,
title = {A New Method for Solving Constraint Satisfaction Problems},
author = {Seidel, Raimund},
booktitle = {Proceedings of the Seventh International Joint Conference on
Artificial Intelligence, {IJCAI-81}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Roger C. Schank},
pages = {338--341},
year = {1981},
month = {8},
note = {INFERENCE and REASONING},
url = {https://ijcai.org/proceedings/1981/66},
}
TY - CPAPER TI - A New Method for Solving Constraint Satisfaction Problems AU - Seidel, Raimund T2 - Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81 PB - International Joint Conferences on Artificial Intelligence PY - 1981 SP - 338 EP - 341 UR - https://ijcai.org/proceedings/1981/66 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
