{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:56:44Z","timestamp":1725537404711},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_68","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"764-775","source":"Crossref","is-referenced-by-count":5,"title":["Disproof of the Neighborhood Conjecture with Implications to SAT"],"prefix":"10.1007","author":[{"given":"Heidi","family":"Gebauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"68_CR1","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A\u00a043, 196\u2013204 (1986)","journal-title":"J. Combin. Theory Ser. A"},{"key":"68_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2002","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons, Chichester (2002)"},{"key":"68_CR3","doi-asserted-by":"crossref","unstructured":"Beck, J.: Combinatorial Games: Tic Tac Toe Theory. Encyclopedia of Mathematics and Its Applications\u00a0114 (2008)","DOI":"10.1017\/CBO9780511735202"},{"key":"68_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01897304","volume":"40","author":"J. Beck","year":"1982","unstructured":"Beck, J.: Remarks on positional games. Acta Math. Acad. Sci. Hungar.\u00a040, 65\u201371 (1982)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"68_CR5","first-page":"229","volume":"23","author":"G. Davydov","year":"1998","unstructured":"Davydov, G., Davydova, I., Kleine B\u00fcning, H.: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF. Artif. Intell.\u00a023, 229\u2013245 (1998)","journal-title":"Artif. Intell."},{"key":"68_CR6","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P. Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Selfridge, J.L.: On a combinatorial game. J. Combinatorial Theory Ser. A\u00a014, 298\u2013301 (1973)","journal-title":"J. Combinatorial Theory Ser. A"},{"key":"68_CR7","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)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"68_CR8","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 J. Discrete Math.\u00a020(2), 523\u2013528 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"1-3","key":"68_CR9","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2005.02.004","volume":"337","author":"S. Hoory","year":"2005","unstructured":"Hoory, S., Szeider, S.: Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable. Theoretical Computer Science\u00a0337(1-3), 347\u2013359 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"68_CR10","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0166-218X(02)00405-5","volume":"130","author":"H. Kleine B\u00fcning","year":"2003","unstructured":"Kleine B\u00fcning, H., Zhao, X.: On the structure of some classes of minimal unsatisfiable formulas. Discr. Appl. Math.\u00a0130(2), 185\u2013207 (2003)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"68_CR11","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 J. Comput.\u00a022(1), 203\u2013210 (1993)","journal-title":"SIAM J. Comput."},{"key":"68_CR12","doi-asserted-by":"crossref","unstructured":"Kullmann, O.: An application of matroid theory to the SAT problem. In: Fifteenth Annual IEEE Conference on Computational Complexity, pp. 116\u2013124 (2000)","DOI":"10.1109\/CCC.2000.856741"},{"key":"68_CR13","doi-asserted-by":"crossref","unstructured":"Moser, R.: A constructive proof of the Lovasz Local Lemma, Eprint, arXiv:0810.4812v2 (2008)","DOI":"10.1145\/1536414.1536462"},{"issue":"1-2","key":"68_CR14","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/S0304-3975(00)00036-0","volume":"238","author":"P. Savick\u00fd","year":"2000","unstructured":"Savick\u00fd, P., Sgall, J.: DNF tautologies with a limited number of occurrences of every variable. Theoret. Comput. Sci.\u00a0238(1-2), 495\u2013498 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"68_CR15","unstructured":"Scheder, D.: Existence, Size, and Resolution Complexity of Almost Disjoint CNF Formulas (submitted)"},{"issue":"2","key":"68_CR16","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/S0166-218X(02)00411-0","volume":"130","author":"S. Szeider","year":"2003","unstructured":"Szeider, S.: Homomorphisms of conjunctive normal forms. Discr. Appl. Math.\u00a0130(2), 351\u2013365 (2003)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"68_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discr. Appl. Math.\u00a08(1), 85\u201389 (1984)","journal-title":"Discr. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_68","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:21:58Z","timestamp":1558538518000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}