| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652620 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
In this paper, we investigate constraint propagation, a mechanism that is run at each basic step of a backtrack search algorithm such as the popular MAC. From a statistical analysis of some relevant features concerning propagation on a large set of graph coloring instances, we show that it is possible to make reasonable predictions about the capability of constraint propagation to detect inconsistency. Using this observation in order to control propagation effort, we show its practical effectiveness.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
