Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||DECOMPOSING CONSTRAINT SATISFACTION PROBLEMS USING DATABASE TECHNIQUES|
|Authors: ||GYSSENS, Marc|
|Issue Date: ||1994|
|Publisher: ||ELSEVIER SCIENCE BV|
|Citation: ||ARTIFICIAL INTELLIGENCE, 66(1). p. 57-89|
|Abstract: ||There is a very close relationship between constraint satisfaction problems and the satisfaction of join-dependencies in a relational database which is due to a common underlying structure, namely a hypergraph. By making that relationship explicit we are able to adapt techniques previously developed for the study of relational databases to obtain new results for constraint satisfaction problems. In particular, we prove that a constraint satisfaction problem may be decomposed into a number of subproblems precisely when the corresponding hypergraph satisfies a simple condition. We show that combining this decomposition approach with existing algorithms can lead to a significant improvement in efficiency.|
|Notes: ||UNIV LONDON,ROYAL HOLLOWAY & BEDFORD NEW COLL,DEPT COMP SCI,EGHAM TW20 0EX,SURREY,ENGLAND. UNIV LIMBURG,DEPT WNI,B-3590 DIEPENBEEK,BELGIUM.|
|ISI #: ||A1994NA73300002|
|Type: ||Journal Contribution|
|Appears in Collections: ||Research publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.