{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:29:41Z","timestamp":1742930981573,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319930305"},{"type":"electronic","value":"9783319930312"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-93031-2_14","type":"book-chapter","created":{"date-parts":[[2018,6,7]],"date-time":"2018-06-07T06:04:24Z","timestamp":1528351464000},"page":"198-214","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["From Backdoor Key to Backdoor Completability: Improving a Known Measure of Hardness for the Satisfiable CSP"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Escamocher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed","family":"Siala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barry","family":"O\u2019Sullivan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,8]]},"reference":[{"key":"14_CR1","unstructured":"Achlioptas, D., Gomes, C.P., Kautz, H.A., Selman, B.: Generating satisfiable problem instances. In: Proceedings of AAAI, IAAI, Austin, Texas, USA, 30 July\u20133 August 2000, pp. 256\u2013261 (2000)"},{"issue":"6","key":"14_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"14_CR3","volume-title":"Constraint Processing","author":"R Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Elsevier\/Morgan Kaufmann, New York City\/Burlington (2003)"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-319-26626-8_54","volume-title":"Combinatorial Optimization and Applications","author":"G Escamocher","year":"2015","unstructured":"Escamocher, G., O\u2019Sullivan, B.: On the minimal constraint satisfaction problem: complexity and generation. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 731\u2013745. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-26626-8_54"},{"issue":"1","key":"14_CR5","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"EC Freuder","year":"1982","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-free search. J. ACM 29(1), 24\u201332 (1982)","journal-title":"J. ACM"},{"key":"14_CR6","unstructured":"Freuder, E.C.: Complexity of K-tree structured constraint satisfaction problems. In: Proceedings of AAAI, Boston, Massachusetts, 29 July\u20133 August 1990, vol. 2, pp. 4\u20139 (1990)"},{"key":"14_CR7","unstructured":"Freuder, E.C.: Completable representations of constraint satisfaction problems. In: Proceedings of KR, Cambridge, MA, USA, 22\u201325 April 1991, pp. 186\u2013195 (1991)"},{"key":"14_CR8","unstructured":"Ganian, R., Ramanujan, M.S., Szeider, S.: Combining treewidth and backdoors for CSP. In: 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, Hannover, Germany, 8\u201311 March 2017, pp. 36:1\u201336:17 (2017)"},{"key":"14_CR9","unstructured":"Gent, I.P., MacIntyre, E., Prosser, P., Walsh, T.: The constrainedness of search. In: Proceedings of AAAI, IAAI, Portland, Oregon, 4\u20138 August 1996, vol. 1, pp. 246\u2013252 (1996)"},{"issue":"4","key":"14_CR10","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s10601-005-2807-z","volume":"10","author":"CP Gomes","year":"2005","unstructured":"Gomes, C.P., Fern\u00e1ndez, C., Selman, B., Bessi\u00e8re, C.: Statistical regimes across constrainedness regions. Constraints 10(4), 317\u2013337 (2005)","journal-title":"Constraints"},{"key":"14_CR11","unstructured":"Hebrard, E.: Mistral, a constraint satisfaction library. In: Proceedings of the Third International CSP Solver Competition, vol. 3, p. 3 (2008)"},{"key":"14_CR12","unstructured":"Kautz, H.A., Ruan, Y., Achlioptas, D., Gomes, C.P., Selman, B., Stickel, M.E.: Balance and filtering in structured satisfiable problems. In: Proceedings of IJCAI, Seattle, Washington, USA, 4\u201310 August 2001, pp. 351\u2013358 (2001)"},{"issue":"1\u20132","key":"14_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","volume":"159","author":"J Larrosa","year":"2004","unstructured":"Larrosa, J., Schiex, T.: Solving weighted CSP by maintaining arc consistency. Artif. Intell. 159(1\u20132), 1\u201326 (2004)","journal-title":"Artif. Intell."},{"key":"14_CR14","unstructured":"L\u00f3pez-Ortiz, A., Quimper, C., Tromp, J., van Beek, P.: A fast and simple algorithm for bounds consistency of the alldifferent constraint. In: Proceedings of IJCAI, Acapulco, Mexico, 9\u201315 August 2003, pp. 245\u2013250 (2003)"},{"issue":"8","key":"14_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic \u2018phase transitions\u2019. Nature 400(8), 133\u2013137 (1999)","journal-title":"Nature"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95\u2013132 (1974)","journal-title":"Inf. Sci."},{"key":"14_CR17","unstructured":"Ruan, Y., Kautz, H.A., Horvitz, E.: The backdoor key: a path to understanding problem hardness. In: Proceedings of AAAI, IAAI, San Jose, California, USA, 25\u201329 July 2004, pp. 124\u2013130 (2004)"},{"issue":"3","key":"14_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoret. Comput. Sci. 47(3), 85\u201393 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90135-0","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR19","unstructured":"Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: Proceedings of IJCAI, Acapulco, Mexico, 9\u201315 August 2003, pp. 1173\u20131178 (2003)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-93031-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T17:28:04Z","timestamp":1709832484000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-93031-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319930305","9783319930312"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-93031-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"8 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delft","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2018\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}