performance of our algorithms during search. Also, it would be interesting to investigate the applicability of similar methods to efficiently achieve or approximate other local consistencies.

## References

[1] T Balafoutis and K. Stergiou. Exploiting constraint weights for revision ordering in Arc Consistency Algorithms. In *ECAI-08 Workshop on Modeling and Solving Problems with Constraints*,
2008.

[2] C. Bessi`ere, J.C. R´egin, R. Yap, and Y. Zhang. An Optimal Coarse-grained Arc Consistency Algorithm. *Artificial Intelligence*, 165(2):165–185, 2005.

[3] F. Boussemart, F. Hemery, and C. Lecoutre. Revision ordering heuristics for the Constraint Satisfaction Problem. In *CP-2004 Workshop on Constraint Propagation*, 2004.

[4] F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais. Boosting systematic search by weighting constraints. In *Proceedings of ECAI-2004*, 2004.

[5] R. Debruyne and C. Bessi`ere. From restricted path consistency to max-restricted path consistency. In *CP-97*, pages 312–326, 1997.

[6] R. Debruyne and C. Bessi`ere. Domain Filtering Consistencies. *JAIR*, 14:205–230, 2001. [7] F. Grandoni and G. Italiano. Improved Algorithms for Max-Restricted Path Consistency. In Proceedings of CP'03, pages 858–862, 2003.

[8] C. Lecoutre and F. Hemery. A study of residual supports in arc cosistency. In Proceedings of IJCAI-2007, pages 125–130, 2007.

[9] C. Likitvivatanavong, Y. Zhang, J. Bowen, S. Shannon, and E. Freuder. Arc Consistency during Search. In *Proceedings of IJCAI-2007*, pages 137–142, 2007.

[10] J. Vion and R. Debruyne. Light Algorithms for Maintaining Max-RPC During Search. In Proceedings of SARA-2009, 2009.

[11] R. Wallace and E. Freuder. Ordering heuristics for arc consistency algorithms. In *AI/GI/VI*,
pages 163–169, Vancouver, British Columbia, Canada, 1992.