Title :
Solving of constraint satisfaction problems using join trees
Author_Institution :
IPF, Karlsruhe Univ., Germany
Abstract :
We provide a new constraint satisfaction system that extends the constraint network to an acyclic one, computes a join tree, and establishes the directional strong k-consistency before any attempt is made to construct a solution; after this, the variables are instantiated without any backtracking. This method is extremely efficient if the constraint network is acyclic and the number of variables per constraint is bounded by a small constant or if a lot of solutions have to be computed
Keywords :
constraint handling; database theory; inference mechanisms; tree data structures; automated reasoning; constraint network; constraint satisfaction problems; hypergraphs; join trees; strong k-consistency; Computer networks; Databases; Electronic mail; Heuristic algorithms; NP-complete problem;
Conference_Titel :
Expert Systems for Development, 1994., Proceedings of International Conference on
Conference_Location :
Bangkok
Print_ISBN :
0-8186-5780-4
DOI :
10.1109/ICESD.1994.302288
