{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T04:10:33Z","timestamp":1743653433555,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_31","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"363-374","source":"Crossref","is-referenced-by-count":6,"title":["Backdoors to Acyclic SAT"],"prefix":"10.1007","author":[{"given":"Serge","family":"Gaspers","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. In: FOCS 2002, pp. 593\u2013603 (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Bacchus, F., Dalmao, S., Pitassi, T.: Algorithms and complexity results for #SAT and Bayesian inference. In: FOCS 2003, pp. 340\u2013351 (2003)","DOI":"10.1109\/SFCS.2003.1238208"},{"issue":"1","key":"31_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci.\u00a05(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"7","key":"31_CR4","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: STOC 1971, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 193\u2013242. Elsevier (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"31_CR7","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann (2003)"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics. Springer (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P. Erd\u0151s","year":"1965","unstructured":"Erd\u0151s, P., P\u00f3sa, L.: On independent circuits contained in a graph. Canadian Journal of Mathematics\u00a017, 347\u2013352 (1965)","journal-title":"Canadian Journal of Mathematics"},{"issue":"4","key":"31_CR11","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.R.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discr. Appl. Math.\u00a0156(4), 511\u2013529 (2008)","journal-title":"Discr. Appl. Math."},{"key":"31_CR12","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer, Berlin (2006)"},{"issue":"2","key":"31_CR13","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica\u00a052(2), 293\u2013307 (2008)","journal-title":"Algorithmica"},{"key":"31_CR14","unstructured":"Franco, J., Martin, J.: A history of satisfiabilty. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, ch. 1, pp. 3\u201397. IOS Press (2009)"},{"key":"31_CR15","unstructured":"Ganian, R., Hlinen\u00fd, P., Obdrz\u00e1lek, J.: Better algorithms for satisfiability problems for formulas of bounded rank-width. In: FSTTCS 2010. LIPIcs, vol.\u00a08, pp. 73\u201383. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"key":"31_CR16","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.R.: Computers and Intractability. W. H. Freeman and Company, New York (1979)"},{"key":"31_CR17","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Szeider, S.: Backdoors to acyclic SAT. Technical Report 1110.6384, arXiv (2011)","DOI":"10.1007\/978-3-642-31594-7_31"},{"key":"31_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-30891-8_15","volume-title":"Fellows Festschrift","author":"S. Gaspers","year":"2012","unstructured":"Gaspers, S., Szeider, S.: Backdoors to Satisfaction. In: Bodlaender, H.L., Downey, R.G., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift. LNCS, vol.\u00a07370, pp. 287\u2013317. Springer, Heidelberg (2012)"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Szeider, S.: Strong backdoors to bounded treewidth SAT. Technical Report 1204.6233, arXiv (2012)","DOI":"10.1109\/FOCS.2013.59"},{"key":"31_CR20","unstructured":"Gaspers, S., Szeider, S.: Strong backdoors to nested satisfiability. In: SAT 2012. LNCS, vol. 7317. Springer (to appear, 2012)"},{"issue":"3","key":"31_CR21","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin, L.: Universal sequential search problems. Problems of Information Transmission\u00a09(3), 265\u2013266 (1973)","journal-title":"Problems of Information Transmission"},{"key":"31_CR22","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: SAT 2004, pp. 96\u2013103 (2004)"},{"issue":"7-8","key":"31_CR23","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00236-007-0056-x","volume":"44","author":"N. Nishimura","year":"2007","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Solving #SAT using vertex covers. Acta Informatica\u00a044(7-8), 509\u2013523 (2007)","journal-title":"Acta Informatica"},{"key":"31_CR24","unstructured":"Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic CNF formulas. In: FSTTCS 2010. LIPIcs, vol.\u00a08, pp. 84\u201395. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"issue":"1","key":"31_CR25","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B\u00a041(1), 92\u2013114 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1-2","key":"31_CR26","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth, D.: On the hardness of approximate reasoning. Artif. Intell.\u00a082(1-2), 273\u2013302 (1996)","journal-title":"Artif. Intell."},{"key":"31_CR27","unstructured":"Samer, M., Szeider, S.: Backdoor trees. In: AAAI 2008, pp. 363\u2013368. AAAI Press (2008)"},{"issue":"1","key":"31_CR28","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jda.2009.06.002","volume":"8","author":"M. Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. J. Discrete Algorithms\u00a08(1), 50\u201364 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"31_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-540-24605-3_15","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Szeider","year":"2004","unstructured":"Szeider, S.: On Fixed-Parameter Tractable Parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 188\u2013202. Springer, Heidelberg (2004)"},{"issue":"1-3","key":"31_CR30","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s10817-005-9007-9","volume":"35","author":"S. Szeider","year":"2005","unstructured":"Szeider, S.: Backdoor sets for DLL subsolvers. Journal of Automated Reasoning\u00a035(1-3), 73\u201388 (2005)","journal-title":"Journal of Automated Reasoning"},{"issue":"2","key":"31_CR31","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"31_CR32","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: IJCAI 2003, pp. 1173\u20131178. Morgan Kaufmann (2003)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:13:06Z","timestamp":1743595986000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}