{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:53:26Z","timestamp":1725512006017},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797180"},{"type":"electronic","value":"9783540797197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79719-7_23","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T08:04:57Z","timestamp":1210061097000},"page":"246-256","source":"Crossref","is-referenced-by-count":2,"title":["How Many Conflicts Does It Need to Be Unsatisfiable?"],"prefix":"10.1007","author":[{"given":"Dominik","family":"Scheder","sequence":"first","affiliation":[]},{"given":"Philipp","family":"Zumstein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/978-3-540-24605-3_32","volume-title":"Theory and Applications of Satisfiability Testing","author":"O. Kullmann","year":"2004","unstructured":"Kullmann, O.: The combinatorics of conflicts between clauses. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 426\u2013440. Springer, Heidelberg (2004)"},{"issue":"2-2","key":"23_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02018930","volume":"9","author":"P. Erd\u0151s","year":"1978","unstructured":"Erd\u0151s, P., Faudree, R.J., Rousseau, C.C., Schelp, R.H.: The size ramsey number. Periodica Mathematica Hungarica\u00a09(2-2), 145\u2013161 (1978)","journal-title":"Periodica Mathematica Hungarica"},{"key":"23_CR3","unstructured":"Faudree, R.J., Schelp, R.H.: A survey of results on the size Ramsey number. In: Paul Erd\u0151s and his mathematics, II (Budapest, 1999), J\u00e1nos Bolyai Math. Soc. Budapest. Bolyai Soc. Math. Stud, vol.\u00a011, pp. 291\u2013309 (2002)"},{"issue":"2","key":"23_CR4","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1137\/S0895480104445745","volume":"20","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Szeider, S.: A note on unsatisfiable k-CNF formulas with few occurrences per variable. SIAM Journal on Discrete Mathematics\u00a020(2), 523\u2013528 (2006)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR5","unstructured":"Welzl, E.: Boolean satisfiability \u2013 combinatorics and algorithms (lecture notes) (2005), \n                  \n                    http:\/\/www.inf.ethz.ch\/~emo\/SmallPieces\/SAT.ps"},{"issue":"1","key":"23_CR6","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0222015","volume":"22","author":"J. Kratochv\u00edl","year":"1993","unstructured":"Kratochv\u00edl, J., Savick\u00fd, P., Tuza, Z.: One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal of Computing\u00a022(1), 203\u2013210 (1993)","journal-title":"SIAM Journal of Computing"},{"key":"23_CR7","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electronic Colloquium on Computational Complexity (ECCC)\u00a010(022) (2003)"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF00881805","volume":"15","author":"J.N. Hooker","year":"1995","unstructured":"Hooker, J.N., Vinay, V.: Branching rules for satisfiability. Journal of Automated Reasoning\u00a015, 359\u2013383 (1995)","journal-title":"Journal of Automated Reasoning"},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/335305.335310","volume-title":"Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing","author":"A. Czumaj","year":"2000","unstructured":"Czumaj, A., Scheideler, C.: A new algorithm approach to the general Lov\u00e1sz local lemma with applications to scheduling and satisfiability problems (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 38\u201347. ACM, New York (2000); (electronic)"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(91)90040-4","volume":"30","author":"P. Erd\u0151s","year":"1991","unstructured":"Erd\u0151s, P., Spencer, J.: Lopsided Lov\u00e1sz local lemma and Latin transversals. Discrete Appl. Math.\u00a030, 151\u2013154 (1991); ARIDAM III (New Brunswick, NJ, 1988)","journal-title":"Discrete Appl. Math."},{"key":"23_CR11","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The probabilistic method, 2nd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York (2000); With an appendix on the life and work of Paul Erd\u0151s","edition":"2"},{"key":"23_CR12","first-page":"13","volume":"14","author":"L. Lu","year":"2007","unstructured":"Lu, L., Sz\u00e9kely, L.: Using Lov\u00e1sz local lemma in the space of random injections. Electron. J. Combin.\u00a014(1), 13 (2007) Research Paper 63 (electronic)","journal-title":"Electron. J. Combin."},{"issue":"1","key":"23_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","volume":"37","author":"C.H. Papadimitriou","year":"1988","unstructured":"Papadimitriou, C.H., Wolfe, D.: The complexity of facets resolved. J. Comput. Syst. Sci.\u00a037(1), 2\u201313 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"23_CR14","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1016\/j.jcss.2004.04.009","volume":"69","author":"S. Szeider","year":"2004","unstructured":"Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. J. Comput. Syst. Sci.\u00a069(4), 656\u2013674 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1-3","key":"23_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(00)00245-6","volume":"107","author":"H. Kleine B\u00fcning","year":"2000","unstructured":"Kleine B\u00fcning, H.: On subclasses of minimal unsatisfiable formulas. Discrete Appl. Math.\u00a0107(1-3), 83\u201398 (2000); Boolean functions and related problems","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"23_CR16","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","volume":"289","author":"H. Fleischner","year":"2002","unstructured":"Fleischner, H., Kullmann, O., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Theoret. Comput. Sci.\u00a0289(1), 503\u2013516 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"1-2","key":"23_CR17","first-page":"1","volume":"3","author":"H. Kleine B\u00fcning","year":"2007","unstructured":"Kleine B\u00fcning, H., Zhao, X.: The complexity of some subclasses of minimal unsatisfiable formulas. J. Satisf. Boolean Model. Comput.\u00a03(1-2), 1\u201317 (2007)","journal-title":"J. Satisf. Boolean Model. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79719-7_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:29:14Z","timestamp":1619522954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79719-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797180","9783540797197"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79719-7_23","relation":{},"subject":[]}}