{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:37:29Z","timestamp":1771702649688,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540428633","type":"print"},{"value":"9783540455783","type":"electronic"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45578-7_11","type":"book-chapter","created":{"date-parts":[[2007,5,28]],"date-time":"2007-05-28T06:34:25Z","timestamp":1180334065000},"page":"153-167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Phase Transitions and Backbones of 3-SAT and Maximum 3-SAT"],"prefix":"10.1007","author":[{"given":"Weixiong","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,19]]},"reference":[{"key":"11_CR1","unstructured":"D. Achlioptas, C. Gomes, H. Kautz, and B. Selman. Generating satisfiable problem instances. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-00), pages 256\u2013261, Austin, Texas, July\u2013August 2000."},{"issue":"4","key":"11_CR2","first-page":"101","volume":"19","author":"J. C. Beck","year":"1998","unstructured":"J. C. Beck and M. S. Fox. A generic framework for constraint-directed search and scheduling. AI Magazine, 19(4):101\u2013130, 1998.","journal-title":"AI Magazine"},{"key":"11_CR3","unstructured":"P. Cheeseman, B. Kanefsky, and W. M. Taylor. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, (IJCAI-91), pages 331\u2013337, Sydney, Australia, August 1991."},{"key":"11_CR4","unstructured":"P. Codognet and F. Rossi. Notes for the ECAI2000 tutorial on Solving and Programming with Soft Constraints: Theory and Practice. Available at \nhttp:\/\/www.math.unipd.it\/frossi\/papers.html\n\n."},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Joseph Culberson and Ian P. Gent. Frozen development in graph coloring. Theoretical Computer Science, page to appear, 2001.","DOI":"10.1016\/S0304-3975(01)00164-5"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann, and D. Loveland. A machine program for theorem proving. Communications of ACM, 5:394\u2013397, 1962.","journal-title":"Communications of ACM"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","volume":"58","author":"E. C. Freuder","year":"1992","unstructured":"E. C. Freuder and R. J. Wallace. Partial constraint satisfaction. Artificial Intelligence, 58:21\u201370, 1992.","journal-title":"Artificial Intelligence"},{"key":"11_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, NY, 1979."},{"key":"11_CR9","unstructured":"I. Gent and T. Walsh. Phase transitions and annealed theories: Number partitioning as a case stud,. In ECAI-96, pages 170\u2013174, 1996."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","volume":"88","author":"I. P. Gent","year":"1996","unstructured":"I. P. Gent and T. Walsh. The TSP phase transition. Artificial Intelligence, 88:349\u2013358, 1996.","journal-title":"Artificial Intelligence"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(95)00044-5","volume":"81","author":"T. Hogg","year":"1996","unstructured":"T. Hogg, B. A. Huberman, and C. Williams. Phase transitions and the search problem. Artificial Intelligence, 81:1\u201315, 1996.","journal-title":"Artificial Intelligence"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0004-3702(87)90033-6","volume":"33","author":"B. A. Huberman","year":"1987","unstructured":"B. A. Huberman and T. Hogg. Phase transitions in artificial intelligence systems. Artificial Intelligence, 33:155\u2013171, 1987.","journal-title":"Artificial Intelligence"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0004-3702(83)80006-X","volume":"21","author":"R. M. Karp","year":"1983","unstructured":"R. M. Karp and J. Pearl. Searching for an optimal path in a tree with random costs. Artificial Intelligence, 21:99\u2013117, 1983.","journal-title":"Artificial Intelligence"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1051\/jphys:019850046080127700","volume":"46","author":"S. Kirkpatrick","year":"1985","unstructured":"S. Kirkpatrick and G. Toulouse. Configuration space analysis of traveling salesman problems. J. de Physique, 46:1277\u20131292, 1985.","journal-title":"J. de Physique"},{"key":"11_CR15","unstructured":"C. J. H. McDiarmid. Probabilistic analysis of tree search. In G. R. Gummett and D. J. A. Welsh, editors, Disorder in Physical Systems, pages 249\u2013260. Oxford Science, 1990."},{"key":"11_CR16","unstructured":"D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92), pages 459\u2013465, San Jose, CA, July 1992."},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic \u2018phase transitions\u2019. Nature, 400:133\u2013137, 1999.","journal-title":"Nature"},{"key":"11_CR18","unstructured":"A. J. Parkes. Clustering at the phase transition. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI-97), pages 340\u2013245, Providence, RI, July, 1997."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1613\/jair.711","volume":"12","author":"J. Singer","year":"2000","unstructured":"J. Singer, I. P. Gent, and A. Smaill. Backbone fragility and the local search cost peak. J. Artificial Intelligence Research, 12:235\u2013270, 2000.","journal-title":"J. Artificial Intelligence Research"},{"key":"11_CR20","unstructured":"J. Slaney and S. Thiebaux. On the hardness of decision and optimisation problems. In Proceedings of ECAI-98, pages 224\u2013248, 1998."},{"key":"11_CR21","unstructured":"J. Slaney and T. Walsh. Backbones in optimization and approximation. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, (IJCAI-01), page to appear, Seattle, WA, August 2001."},{"key":"11_CR22","volume-title":"Foundations of Constraint Satisfaction","author":"E. Tsang","year":"1993","unstructured":"E. Tsang. Foundations of Constraint Satisfaction. Academic Press, London, 1993."},{"key":"11_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1538-7","volume-title":"State-Space Search: Algorithms, Complexity, Extensions, and Applications","author":"W. Zhang","year":"1999","unstructured":"W. Zhang. State-Space Search: Algorithms, Complexity, Extensions, and Applications. Springer, New York, NY, 1999."},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0004-3702(94)00047-6","volume":"79","author":"W. Zhang","year":"1995","unstructured":"W. Zhang and R. E. Korf. Performance of linear-space search algorithms. Artificial Intelligence, 79:241\u2013292, 1995.","journal-title":"Artificial Intelligence"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0004-3702(95)00054-2","volume":"81","author":"W. Zhang","year":"1996","unstructured":"W. Zhang and R. E. Korf. A study of complexity transitions on the asymmetric Traveling Salesman Problem. Artificial Intelligence, 81:223\u2013239, 1996.","journal-title":"Artificial Intelligence"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2014 CP 2001"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45578-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,30]],"date-time":"2020-03-30T21:07:38Z","timestamp":1585602458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45578-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540428633","9783540455783"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-45578-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"19 November 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}