Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/3795
Title: DECOMPOSING CONSTRAINT SATISFACTION PROBLEMS USING DATABASE TECHNIQUES
Authors: GYSSENS, Marc 
JEAVONS, PG
COHEN, DA
Issue Date: 1994
Publisher: ELSEVIER SCIENCE BV
Source: 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.
Document URI: http://hdl.handle.net/1942/3795
ISI #: A1994NA73300002
Type: Journal Contribution
Appears in Collections:Research publications

Show full item record

WEB OF SCIENCETM
Citations

97
checked on May 22, 2022

Page view(s)

42
checked on May 27, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.