References

1

Y. Asahiro, K. Iwama, and E. Miyano. Random generation of test instances with controlled attributes. In Second DIMACS Challenge Workshop, 1993.

2

Roberto J. Bayardo, Jr. and Robert Schrag. Using CSP look-back techniques to solve exceptionally hard SAT instances. In Eugene C. Freuder, editor, Principles and Practice of Constraint Programming - CP96, pages 46-60, Cambridge, MA, 1996. Springer.

3

B. Cha and K. Iwama. Performance test of local search algorithms using new types of random CNF formulas. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 304-310, Montréal, Québec, Canada, 1995.

4

P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, pages 331-337, Sydney, Australia, 1991.

5

J. M. Crawford and L. D. Auton. Experimental results on the cross-over point in satisfiability problems. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pages 21-27, Washington, DC, USA, 1993.

6

Ian P. Gent, Ewan MacIntyre, Patrick Prosser, and Toby Walsh. Scaling effects in the CSP phase transition. In U. Montanari and F. Rossi, editors, Proc. of Principles and Practices of Constraint Programming PPCP95, pages 70-87. Springer-Verlag, 1995.

7

Ian P. Gent and Toby Walsh. Easy problems are sometimes hard. Artificial Intelligence, 70:335-345, 1994.

8

Ian P. Gent and Toby Walsh. The SAT phase transition. In A.G. Cohn, editor, Proceedings of the ECAI-94, pages 105-109. John Wiley and Sons, 1994.

9

Ian P. Gent and Toby Walsh. The satisfiability constraint gap. Artificial Intelligence, 81(1-2):59-80, 1996.

10

Matthew L. Ginsberg. Dynamic backtracking. Journal of Artificial Intelligence Research, 1:25-46, 1993.

11

Tad Hogg. Refining the phase transitions in combinatorial search. Artificial Intelligence, 81:127-154, 1996.

12

Tad Hogg and Colin P. Williams. The hardest constraint problems: A double phase transition. Artificial Intelligence, 69:359-377, 1994.

13

David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon. Optimization by simulated annealing: An experimental evaluation; part II, Graph coloring and number partitioning. Operations Research, 39(3):378-406, 1991.

14

Kalev Kask and Rina Dechter. GSAT and local consistency. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 616-622, Montréal, Québec, Canada, 1995.

15

Scott Kirkpatrick and Bart Selman. Critical behavior in the satisfiability of random boolean expressions. Science, 264:1297-1301, 1994.

16

D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the Tenth National Conference on Artificial Intelligence, pages 459-465, San Jose, CA, USA, 1992.

17

Patrick Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81:81-109, 1996.

18

Barbara M. Smith. Phase transition and the mushy region in constraint satisfaction problems. In A.G. Cohn, editor, Proceedings of the ECAI-94, pages 100-104. John Wiley and Sons, 1994.

19

Barbara M. Smith and Martin E. Dyer. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81:155-181, 1996.

20

George W. Snedecor and William G. Cochran. Statistical Methods. Iowa State Univ. Press, Ames, Iowa, 6th edition, 1967.

21

C. P. Williams and T. Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence, 70:73-117, 1994.

22

Nobuhiro Yugami, Yuiko Ohta, and Hirotaka Hara. Improving repair-based constraint satisfaction methods by value propagation. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 344-349, Seattle, WA, USA, 1994.

Previous: 7. Acknowledgements
Return to Contents