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
102
checked on Sep 28, 2024
Page view(s)
72
checked on Oct 29, 2023
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.