{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:47:52Z","timestamp":1751582872588,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343752"},{"type":"electronic","value":"9783540343783"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_9","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T10:34:15Z","timestamp":1149244455000},"page":"60-68","source":"Crossref","is-referenced-by-count":9,"title":["Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Dantsin","sequence":"first","affiliation":[]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wolpert","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"issue":"1-3","key":"9_CR2","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T. Brueggemann","year":"2004","unstructured":"Brueggemann, T., Kern, W.: An improved local search algorithm for 3-SAT. Theoretical Computer Science\u00a0329(1-3), 303\u2013313 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9_CR3","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 deterministic (2\u2009\u2212\u20092\/(k\u2009+\u20091)) n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-540-24749-4_13","volume-title":"STACS 2004","author":"E. Dantsin","year":"2004","unstructured":"Dantsin, E., Hirsch, E.A., Wolpert, A.: Algorithms for SAT based on search in Hamming balls. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 141\u2013151. Springer, Heidelberg (2004)"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/11527695_7","volume-title":"Theory and Applications of Satisfiability Testing","author":"E. Dantsin","year":"2005","unstructured":"Dantsin, E., Wolpert, A.: Derandomization of Schuler\u2019s algorithm for SAT. In: Hoos, H.H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 80\u201388. Springer, Heidelberg (2005)"},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.3233\/SAT190002","volume":"1","author":"E. Dantsin","year":"2005","unstructured":"Dantsin, E., Wolpert, A.: A faster clause-shortening algorithm for SAT with no restriction on clause length. Journal on Satisfiability, Boolean Modeling and Computation\u00a01, 49\u201360 (2005)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, January 2004, p. 328 (2004)","key":"9_CR7"},{"doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1998, pp. 628\u2013637 (1998)","key":"9_CR8","DOI":"10.1109\/SFCS.1998.743513"},{"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, FOCS 1997, pp. 566\u2013574 (1997)","key":"9_CR9","DOI":"10.1109\/SFCS.1997.646146"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BFb0055762","volume-title":"Mathematical Foundations of Computer Science 1998","author":"P. Pudl\u00e1k","year":"1998","unstructured":"Pudl\u00e1k, P.: Satisfiability \u2013 algorithms and logic. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds.) MFCS 1998. LNCS, vol.\u00a01450, pp. 129\u2013141. Springer, Heidelberg (1998)"},{"doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1999, pp. 410\u2013414 (1999)","key":"9_CR11","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"1","key":"9_CR12","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.jalgor.2004.04.012","volume":"54","author":"R. Schuler","year":"2003","unstructured":"Schuler, R.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms\u00a054(1), 40\u201344 (2003), A preliminary version appeared as a technical report in 2003","journal-title":"Journal of Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Stanley, R.P.: Enumerative Combinatorics, vol.\u00a01. Wadsworth & Brooks\/Cole (1986)","key":"9_CR13","DOI":"10.1007\/978-1-4615-9763-6_1"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:17:06Z","timestamp":1736399826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11758471_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}