{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T23:05:52Z","timestamp":1778886352972,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540615514","type":"print"},{"value":"9783540706205","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61551-2_70","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:57:17Z","timestamp":1330293437000},"page":"119-133","source":"Crossref","is-referenced-by-count":34,"title":["Local search and the number of solutions"],"prefix":"10.1007","author":[{"given":"David A.","family":"Clark","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Frank","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian P.","family":"Gent","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ewan","family":"MacIntyre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neven","family":"Tomov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toby","family":"Walsh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D. Brelaz","year":"1979","unstructured":"D. Brelaz. New methods to color the vertices of a graph. Comms. ACM, 22:251\u2013256, 1979.","journal-title":"Comms. ACM"},{"key":"9_CR2","unstructured":"P. Cheeseman, B. Kanefsky, and W.M. Taylor. Where the really hard problems are. In Proceedings, IJCAI-91, pages 331\u2013337, 1991."},{"key":"9_CR3","unstructured":"J.M. Crawford and L.D. Auton. Experimental results on the crossover point in satisfiability problems. In Proceedings, AAAI-93, pages 21\u201327, 1993."},{"key":"9_CR4","unstructured":"A. Davenport. A comparison of complete and incomplete algorithms in the easy and hard regions. In Proceedings, Workshop on Studying and Solving Really Hard Problems, CP-95, pages 43\u201351, 1995."},{"key":"9_CR5","unstructured":"J. Frank and C. Martel. Phase transitions in random graphs. In Proceedings, Workshop on Studying and Solving Really Hard Problems, CP-95, 1995."},{"key":"9_CR6","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, 1979."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. Scaling effects in the CSP phase transition. In Proceedings, CP-95, pages 70\u201387, 1995.","DOI":"10.1007\/3-540-60299-2_5"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. The constrainedness of search. In Proceedings, AAAI-96, 1996.","DOI":"10.1007\/BFb0017449"},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1613\/jair.7","volume":"1","author":"I.P. Gent","year":"1993","unstructured":"I.P. Gent and T. Walsh. An empirical analysis of search in GSAT. Journal of Artificial Intelligence Research, 1:47\u201359, September 1993.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9_CR10","unstructured":"I.P. Gent and T. Walsh. Unsatisfied variables in local search. In Hybrid Problems, Hybrid Solutions, pages 73\u201385. IOS Press, 1995. Proceedings, AISB-95."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","volume":"7","author":"A. Kamath","year":"1995","unstructured":"A. Kamath, R. Motwani, K. Palem, and P. Spirakis. Tail bounds for occupancy and the satisfiability threshold conjecture. Randomized Structure and Algorithms, 7:59\u201380, 1995.","journal-title":"Randomized Structure and Algorithms"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"S. A. Kauffman. The Origins of Order. Oxford University Press, 1993.","DOI":"10.1093\/oso\/9780195079517.001.0001"},{"key":"9_CR13","unstructured":"S. Minton, M. D. Johnston, A. B. Philips, and P. Laird. Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In Proceedings, AAAI-90, pages 17\u201324, 1990."},{"key":"9_CR14","unstructured":"D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings, AAAI-92, pages 459\u2013465, 1992."},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","volume":"9","author":"P. Prosser","year":"1993","unstructured":"P. Prosser. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9:268\u2013299, 1993.","journal-title":"Computational Intelligence"},{"key":"9_CR16","unstructured":"P. Prosser. Binary constraint satisfaction problems: Some are harder than others. In Proceedings, ECAI-94, pages 95\u201399, 1994."},{"key":"9_CR17","unstructured":"B. Selman, H. Kautz, and B. Cohen. Noise Strategies for Improving Local Search. In Proceedings, AAAI-94, pages 337\u2013343, 1994."},{"key":"9_CR18","unstructured":"B. Selman, H. Levesque, and D. Mitchell. A new method for solving hard satisfiability problems. In Proceedings, AAAI-92, 1992."},{"key":"9_CR19","unstructured":"B.M. Smith. Phase transition and the mushy region in constraint satisfaction problems. In Proceedings, ECAI-94, pages 100\u2013104, 1994."},{"key":"9_CR20","unstructured":"N. Tomov. Hill-climbing heuristics for solving constraint satisfaction problems. 4th year project report, Department of Artificial Intelligence, University of Edinburgh 1994."},{"key":"9_CR21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","volume":"70","author":"C.P. Williams","year":"1994","unstructured":"C.P. Williams and T. Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence, 70:73\u2013117, 1994.","journal-title":"Artificial Intelligence"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2014 CP96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61551-2_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:21:56Z","timestamp":1742599316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61551-2_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615514","9783540706205"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-61551-2_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}