D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy et al., Random Constraint Satisfaction: a More Accurate Picture, Proceedings CP'97, pp.107-120, 1997.

R. Bayardo and D. Miranker, A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem, Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), pp.558-562, 1996.

D. L. Berre and L. Simon, Fifty-five solvers in vancouver: The sat 2004 competition, Proceedings of SAT'04, 2004.

C. Bessière and J. Régin, MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems, Proceedings CP'96, pp.61-75, 1996.

C. Bessière, B. Zanuttini, and C. Fernández, Measuring Search Trees, Proceedings ECAI'04 Workshop on Modelling and Solving Problems with Constraints, 2004.

H. Chen, C. Gomes, and B. Selman, Formal Models of Heavy-tailed Behavior in Combinatorial Search, Proceedings CP'01, pp.408-421, 2001.

R. Dechter, Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition', Artificial Intelligence, vol.41, issue.3, pp.273-312, 1990.

R. Dechter, Constraint Processing, 2003.

D. Frost, I. Rish, and L. Vila, Summarizing CSP Hardness with Continuous Probability Distributions, AAAI-97, pp.327-333, 1997.

J. Gaschnig, A General Backtrack Algorithm that Eliminates Most Redundant Tests, Proceedings IJCAI'77, p.447, 1977.

I. Gent and T. Walsh, Easy Problems are Sometimes Hard, Artificial Intelligence, vol.70, pp.335-345, 1994.

C. Gomes, B. Selman, and N. Crato, Heavy-tailed Distributions in Combinatorial Search, Proceedings CP'97, pp.121-135, 1997.

C. P. Gomes, B. Selman, N. Crato, and H. Kautz, Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, J. of Automated Reasoning, vol.24, issue.1-2, pp.67-100, 2000.

R. Haralick and G. Elliot, Increasing Tree Search Efficiency for Constraint Satisfaction Problems, Artificial Intelligence, vol.14, pp.263-313, 1980.

T. Hogg, B. Huberman, and C. Williams, Phase Transitions and Search Problems'. Artificial Intelligence, vol.81, issue.1-2, pp.1-15, 1996.

T. Hogg and C. Williams, The Hardest Constraint Problems: a Double Phase Transition, Artificial Intelligence, vol.69, pp.359-377, 1994.

H. H. Hoos and T. Stützle, Stochastic Local Search: Foundations and Applications, 2004.

E. Horvitz, Y. Ruan, C. Gomes, H. Kautz, B. Selman et al., A Bayesian Approach to Tackling Hard Computational Problems, Proceedings of the Seventeenth Conference On Uncertainty in Artificial Intelligence (UAI-01), 2001.

H. Kautz, E. Horvitz, Y. Ruan, C. Gomes, and B. Selman, Dynamic Restart Policies, Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), 2002.

C. Li and . Ambulagan, Heuristics Based on Unit Propagation for Satisfiability Problems, Proceedings IJCAI'97, pp.366-371, 1997.

J. P. Marques-silva and K. A. Sakallah, GRASP -A search algorithm for propositional satisfiability, IEEE Transactions on Computers, vol.48, issue.5, pp.506-521, 1999.

R. Mohr and T. Henderson, Arc and Path Consistency Revisited, Artificial Intelligence, vol.28, pp.225-233, 1986.
URL : https://hal.archives-ouvertes.fr/inria-00548487

M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, and S. Malik, Chaff: Engineering an Efficient SAT Solver, Proceedings of the 39th Design Automation Conference, 2001.

B. Nadel, Constraint Satisfaction Algorithms'. Computational Intelligence, vol.5, pp.188-224, 1989.

P. Prosser, Domain Filtering Can Degrade Intelligent Backtrack Search, Proceedings IJCAI'93, pp.262-267, 1993.

P. Prosser, Hybrid algorithms for the constraint satisfaction problem', Computational Intelligence, vol.9, issue.3, pp.268-299, 1993.

I. Rish and R. Dechter, Resolution versus Search: Two Strategies for SAT, J. of Automated Reasoning, vol.24, issue.1/2, pp.225-275, 2000.

D. Sabin and E. Freuder, Contradicting Conventional Wisdom in Constraint Satisfaction, Proceedings PPCP'94, 1994.

B. Selman and S. Kirkpatrick, Finite-Size Scaling of the Computational Cost of Systematic Search', Artificial Intelligence, vol.81, issue.1-2, pp.273-295, 1996.

B. Smith and S. Grant, Sparse Constraint Graphs and Exceptionally Hard Problems, Proceedings IJCAI'95. Montral, pp.646-651, 1995.

B. Smith and S. Grant, Modelling Exceptionally Hard Constraint Satisfaction Problems, Proceedings CP'97, pp.182-195, 1997.

T. Walsh, SAT vs CSP, Proceedings CP'00, pp.441-456, 2000.

R. Williams, C. Gomes, and B. Selman, Backdoors to Typical Case Complexity, 2003.

R. Williams, C. Gomes, and B. Selman, On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search, Proceedings of Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT-03), 2003.

K. Xu and W. Li, Exact Phase Transition in Random Constraint Satisfaction Problems, vol.12, pp.93-103, 2000.