{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:25:10Z","timestamp":1725513910769},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540727873"},{"type":"electronic","value":"9783540727880"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72788-0_12","type":"book-chapter","created":{"date-parts":[[2007,6,28]],"date-time":"2007-06-28T12:25:22Z","timestamp":1183033522000},"page":"94-99","source":"Crossref","is-referenced-by-count":2,"title":["Matched Formulas and Backdoor Sets"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Szeider","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"12_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":"12_CR2","unstructured":"Bidyuk, B., Dechter, R.: On finding minimal w-cutset problem. In: UAI 2004, 20th Conference on Uncertainty in Artificial Intelligence (2004)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Dantchev, S., Martin, B., Szeider, S.: Parameterized proof complexity: a complexity gap for parameterized tree-like resolution. Technical Report TR07-001, Electronic Colloquium on Computational Complexity (ECCC) (Jan. 2007)","DOI":"10.1109\/FOCS.2007.53"},{"key":"12_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"1","key":"12_CR5","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."},{"volume-title":"Parameterized Complexity Theory","year":"2006","author":"J. Flum","key":"12_CR6","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0166-218X(01)00358-4","volume":"125","author":"J. Franco","year":"2003","unstructured":"Franco, J., Van Gelder, A.: A perspective on certain polynomial time solvable classes of satisfiability. Discr. Appl. Math.\u00a0125, 177\u2013214 (2003)","journal-title":"Discr. Appl. Math."},{"volume-title":"Computers and Intractability","year":"1979","author":"M.R. Garey","key":"12_CR8","unstructured":"Garey, M.R., Johnson, D.R.: Computers and Intractability. W.H. Freeman, New York (1979)"},{"issue":"1\u20133","key":"12_CR9","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. Discr. Appl. Math.\u00a0107(1\u20133), 83\u201398 (2000)","journal-title":"Discr. Appl. Math."},{"key":"12_CR10","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","first-page":"96","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. Nishimura","year":"2005","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: H. Hoos, H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 96\u2013103. Springer, Heidelberg (2005)"},{"key":"12_CR12","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)"},{"issue":"4","key":"12_CR13","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. of Computer and System Sciences\u00a069(4), 656\u2013674 (2004)","journal-title":"J. of Computer and System Sciences"},{"issue":"1-4","key":"12_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10472-004-9432-1","volume":"43","author":"S. Szeider","year":"2005","unstructured":"Szeider, S.: Generalizations of matched CNF formulas. Ann. Math. Artif. Intell.\u00a043(1-4), 223\u2013238 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"1","key":"12_CR15","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."},{"key":"12_CR16","unstructured":"Williams, R., Gomes, C., Selman, B.: On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In: SAT 2003, Informal Proceedings, pp. 222\u2013230 (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72788-0_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T18:33:18Z","timestamp":1683916398000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72788-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540727873","9783540727880"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72788-0_12","relation":{},"subject":[]}}