{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:53:29Z","timestamp":1725512009760},"publisher-location":"Berlin, Heidelberg","reference-count":16,"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_16","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T08:04:57Z","timestamp":1210061097000},"page":"161-167","source":"Crossref","is-referenced-by-count":3,"title":["A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Kottler","sequence":"first","affiliation":[]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Carsten","family":"Sinz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Proc. Lett.\u00a08, 121\u2013123 (1979)","journal-title":"Inf. Proc. Lett."},{"issue":"1-3","key":"16_CR2","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T. Br\u00fcggemann","year":"2004","unstructured":"Br\u00fcggemann, T., Kern, W.: An improved deterministic local search algorithm for 3-sat. Theor. Comput. Sci.\u00a0329(1-3), 303\u2013313 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR3","unstructured":"del Val, A.: On 2-SAT and renamable horn. In: AAAI: 17th National Conference on Artificial Intelligence, AAAI \/ MIT Press (2000)"},{"key":"16_CR4","unstructured":"Fernau, H.: A top-down approach to search-trees: Improved algorithmics for 3-hitting set. Electronic Colloquium on Computational Complexity, TR04-073 (2004)"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(02)00401-8","volume":"130","author":"J. Franco","year":"2003","unstructured":"Franco, J., Swaminathan, R.: On good algorithms for determining unsatisfiability of propositional formulas. Discrete Appl. Math.\u00a0130(2), 129\u2013138 (2003)","journal-title":"Discrete Appl. Math."},{"key":"16_CR6","unstructured":"Interian, Y.: Backdoor sets for random 3-sat. In: SAT (2003)"},{"key":"16_CR7","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Universit\u00e4t T\u00fcbingen (October 2002)"},{"key":"16_CR8","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to horn and binary clauses. In: SAT (2004)"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11814948_36","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"N. Nishimura","year":"2006","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Solving #SAT using vertex covers. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 396\u2013409. Springer, Heidelberg (2006)"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/11527695_20","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Porschen","year":"2005","unstructured":"Porschen, S., Speckenmeyer, E.: Worst Case Bounds for Some NP-Complete Modified Horn-SAT Problems. In: H. Hoos, H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 251\u2013262. Springer, Heidelberg (2005)"},{"issue":"11","key":"16_CR11","doi-asserted-by":"publisher","first-page":"1408","DOI":"10.1016\/j.dam.2007.02.010","volume":"155","author":"S. Porschen","year":"2007","unstructured":"Porschen, S., Speckenmeyer, E.: Satisfiability of mixed Horn formulas. Discrete Applied Mathematics\u00a0155(11), 1408\u20131419 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR12","unstructured":"Ruan, Y., Kautz, H.A., Horvitz, E.: The backdoor key: A path to understanding problem hardness. In: AAAI, pp. 124\u2013130 (2004)"},{"key":"16_CR13","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: Symposium on Foundations of Computer Science (1999)"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-540-72788-0_12","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2007","author":"S. Szeider","year":"2007","unstructured":"Szeider, S.: Matched Formulas and Backdoor Sets. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol.\u00a04501, pp. 94\u201399. Springer, Heidelberg (2007)"},{"key":"16_CR15","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures, and upper bounds for satisfiability and related problems. PhD thesis, Link\u00f6ping University, Dissertation no 1079 (2007)"},{"key":"16_CR16","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: IJCAI (2003)"}],"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_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:29:10Z","timestamp":1619522950000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79719-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797180","9783540797197"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79719-7_16","relation":{},"subject":[]}}