{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:53:12Z","timestamp":1743144792202,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642210426"},{"type":"electronic","value":"9783642210433"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21043-3_33","type":"book-chapter","created":{"date-parts":[[2011,5,24]],"date-time":"2011-05-24T12:36:15Z","timestamp":1306240575000},"page":"269-280","source":"Crossref","is-referenced-by-count":4,"title":["Finding Small Backdoors in SAT Instances"],"prefix":"10.1007","author":[{"given":"Zijie","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"van Beek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"7","key":"33_CR1","first-page":"394","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem proving. Commun.\u00a0ACM\u00a05(7), 394\u2013397 (1962)","journal-title":"Commun.\u00a0ACM"},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-540-74970-7_20","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2007","author":"B. Dilkina","year":"2007","unstructured":"Dilkina, B., Gomes, C.P., Sabharwal, A.: Tradeoffs in the complexity of backdoor detection. In: Bessi\u00e8re, C. (ed.) CP 2007. LNCS, vol.\u00a04741, pp. 256\u2013270. Springer, Heidelberg (2007)"},{"key":"33_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-02777-2_9","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"B. Dilkina","year":"2009","unstructured":"Dilkina, B., Gomes, C.P., Sabharwal, A.: Backdoors in the context of learning. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol.\u00a05584, pp. 73\u201379. Springer, Heidelberg (2009)"},{"key":"33_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/978-3-540-85958-1_53","volume-title":"Principles and Practice of Constraint Programming","author":"P. Gregory","year":"2008","unstructured":"Gregory, P., Fox, M., Long, D.: A new empirical study of weak backdoors. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol.\u00a05202, pp. 618\u2013623. Springer, Heidelberg (2008)"},{"key":"33_CR5","first-page":"283","volume-title":"SAT 2000","author":"H.H. Hoos","year":"2000","unstructured":"Hoos, H.H., St\u00fctzle, T.: SATLIB: An online resource for research on SAT. In: Gent, I.P., Maaren, H.v., Walsh, T. (eds.) SAT 2000, pp. 283\u2013292. IOS Press, Amsterdam (2000)"},{"key":"33_CR6","unstructured":"Interian, Y.: Backdoor sets for random 3-SAT. Paper presented at SAT 2003 (2003)"},{"key":"33_CR7","unstructured":"Kilby, P., Slaney, J., Thi\u00e9baux, S., Walsh, T.: Backbones and backdoors in satisfiability. In: Proc.\u00a0of AAAI, pp. 1368\u20131373 (2005)"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-79719-7_15","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2008","author":"S. Kottler","year":"2008","unstructured":"Kottler, S., Kaufmann, M., Sinz, C.: Computation of Renameable Horn Backdoors. In: Kleine B\u00fcning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol.\u00a04996, pp. 154\u2013160. Springer, Heidelberg (2008)"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Paris, L., Ostrowski, R., Siegel, P., Sais, L.: Computing Horn strong backdoor sets thanks to local search. In: Proc.\u00a0of ICTAI, pp. 139\u2013143 (2006)","DOI":"10.1109\/ICTAI.2006.43"},{"key":"33_CR10","unstructured":"Ruan, Y., Kautz, H., Horvitz, E.: The backdoor key: A path to understanding problem hardness. In: Proc.\u00a0of AAAI, pp. 124\u2013130 (2004)"},{"key":"33_CR11","unstructured":"Samer, M., Szeider, S.: Backdoor trees. In: Proc.\u00a0of AAAI, pp. 363\u2013368 (2008)"},{"issue":"1","key":"33_CR12","first-page":"75","volume":"17","author":"C. Sinz","year":"2003","unstructured":"Sinz, C., Kaiser, A., K\u00fcchlin, W.: Formal methods for the validation of automotive product configuration data. AI EDAM\u00a017(1), 75\u201397 (2003)","journal-title":"AI EDAM"},{"key":"33_CR13","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Proc.\u00a0of IJCAI, pp. 1173\u20131178 (2003)"},{"key":"33_CR14","unstructured":"Williams, R., Gomes, C., Selman, B.: On the connections between backdoors and heavy-tails on combinatorial search. Paper presented at SAT 2003 (2003)"}],"container-title":["Lecture Notes in Computer Science","Advances in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21043-3_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T05:51:23Z","timestamp":1558590683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21043-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642210426","9783642210433"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21043-3_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}