The power of propagation : when GAC is enough
- Submitting institution
-
Royal Holloway and Bedford New College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 29010830
- Type
- D - Journal article
- DOI
-
10.1007/s10601-016-9251-0
- Title of journal
- Constraints
- Article number
- -
- First page
- 3
- Volume
- 22
- Issue
- -
- ISSN
- 1572-9354
- Open access status
- Out of scope for open access requirements
- Month of publication
- August
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 5
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The most important propagation practical technique for pre-processing and helping to solve Constraint Problems (CP) is Generalised Arc Consistency (GAC). Despite the essential nature of GAC to the discipline, there has been no general theory to explain why pre-processing with GAC solves completely some CP instances. Here we completely characterise and explain this phenomenon, and proves some corresponding hardness results. Because of its importance in explaining such a basic question this paper won a journal paper track award at CP'16 - the international conference for the CP community.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -