Journal article icon

Journal article

Fast and parallel decomposition of constraint satisfaction problems

Abstract:

Constraint Satisfaction Problems (CSP) are notoriously hard. Consequently, powerful decomposition methods have been developed to overcome this complexity. However, this poses the challenge of actually computing such a decomposition for a given CSP instance, and previous algorithms have shown their limitations in doing so. In this paper, we present a number of key algorithmic improvements and parallelisation techniques to compute so-called Generalized Hypertree Decompositions (GHDs) faster. We...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1007/s10601-022-09332-1

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St John's College
Role:
Author
Publisher:
Springer Publisher's website
Journal:
Constraints Journal website
Volume:
27
Pages:
284–326
Publication date:
2022-06-03
Acceptance date:
2022-04-23
DOI:
EISSN:
1572-9354
ISSN:
1383-7133
Language:
English
Keywords:
Pubs id:
1260218
Local pid:
pubs:1260218
Deposit date:
2022-05-21

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP