{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:39:09Z","timestamp":1742913549984,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":12,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_45","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:37Z","timestamp":1214505397000},"page":"83-86","source":"Crossref","is-referenced-by-count":0,"title":["Backtracking Based k-SAT Algorithms"],"prefix":"10.1007","author":[{"given":"Ramamohan","family":"Paturi","sequence":"first","affiliation":[]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[]},{"given":"Francis","family":"Zane","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1_45","doi-asserted-by":"crossref","unstructured":"Baumer, S., Schuler, R.: Improving a\u00a0Probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs. In: SAT 2003, pp. 150\u2013161","DOI":"10.1007\/978-3-540-24605-3_12"},{"key":"45_CR2_45","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. In: Proceedings of the Eighteenth IEEE Conference on Computational Complexity, 2003"},{"issue":"1","key":"45_CR3_45","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A\u00a0deterministic $$ { (2-\\frac{2}{k+1})^n } $$ algorithm for k-SAT based on local search. Theor. Comp. Sci. 289(1), 69\u201383 (2002)","journal-title":"Theor. Comp. Sci."},{"key":"45_CR4_45","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A\u00a0machine program for theorem proving. Commun. ACM 5, 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"key":"45_CR5_45","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-45841-7_15","volume-title":"STACS 2002. LNCS, vol. 2285","author":"T. Hofmeister","year":"2002","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A\u00a0probabilistic 3\u2013SAT algorithm further improved. In: STACS 2002. LNCS, vol.\u00a02285, pp. 192\u2013202. Springer, Berlin (2002)"},{"key":"45_CR6_45","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, 2004, pp. 328\u2013329"},{"issue":"1\u20132","key":"45_CR7_45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comp. Sci. 223(1\u20132), 1\u201372 (1999)","journal-title":"Theor. Comp. Sci."},{"key":"45_CR8_45","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Solving Satisfiability In Less Than 2 n Steps. Discret. Appl. Math. 10, 287\u2013295 (1985)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"45_CR9_45","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R. Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M., Zane, F.: An Improved Exponential\u2010time Algorithm for k-SAT. J.\u00a0ACM 52(3), 337\u2013364 (2005) (An earlier version presented in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 628\u2013637)","journal-title":"J. ACM"},{"key":"45_CR10_45","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability Coding Lemma. In: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 566\u2013574. Chicago J. Theor. Comput. Sci. (1999), http:\/\/cjtcs.cs.uchicago.edu\/","DOI":"10.1109\/SFCS.1997.646146"},{"key":"45_CR11_45","unstructured":"Rolf, D.: 3-SAT \u2208 RTIME $$ { (1.32971^n) } $$. In: ECCC TR03-054, 2003"},{"key":"45_CR12_45","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning, U.: A\u00a0probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32, 615\u2013623 (2002) (An earlier version appeared in 40th Annual Symposium on Foundations of Computer Science (FOCS '99), pp. 410\u2013414)","journal-title":"Algorithmica"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T21:32:36Z","timestamp":1738272756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_45"}},"subtitle":["2005; Paturi, Pudl\u00e1k, Saks, Zane"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_45","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}