www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
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.
URI: http://hdl.handle.net/1942/3795
ISI #: A1994NA73300002
ISSN: 0004-3702
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.