{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:56:07Z","timestamp":1725688567086},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642316111"},{"type":"electronic","value":"9783642316128"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31612-8_7","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T05:14:42Z","timestamp":1339996482000},"page":"72-85","source":"Crossref","is-referenced-by-count":2,"title":["Strong Backdoors to Nested Satisfiability"],"prefix":"10.1007","author":[{"given":"Serge","family":"Gaspers","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"7_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"7_CR2","unstructured":"Biedl, T., Henderson, P.: Nested SAT graphs have treewidth three. Technical Report CS-2004-70. University of Waterloo (2004)"},{"issue":"6","key":"7_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proc. of STOC 1971, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"7_CR5","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":"7_CR6","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-540-74970-7_20","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2007","author":"B.N. Dilkina","year":"2007","unstructured":"Dilkina, B.N., Gomes, C.P., Sabharwal, A.: Tradeoffs in the Complexity of Backdoor Detection. In: Bessi\u00e8re, C. (ed.) CP 2007. LNCS, vol.\u00a04741, pp. 256\u2013270. Springer, Heidelberg (2007)"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"3","key":"7_CR9","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM\u00a035(3), 727\u2013739 (1988)","journal-title":"J. ACM"},{"issue":"4","key":"7_CR10","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":"7_CR11","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer (2006)"},{"key":"7_CR12","unstructured":"Gaspers, S.: From edge-disjoint paths to independent paths. Technical Report 1203.4483, arXiv (2012)"},{"key":"7_CR13","series-title":"LNCS","first-page":"363","volume-title":"ICALP 2012, Part I","author":"S. Gaspers","year":"2012","unstructured":"Gaspers, S., Szeider, S.: Backdoors to Acyclic SAT. In: Czumaj, A., et al. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 363\u2013374. Springer, Heidelberg (2012)"},{"key":"7_CR14","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":"7_CR15","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":"7_CR16","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Szeider, S.: Strong backdoors to nested satisfiability. Technical Report 1202.4331, arXiv (2012)","DOI":"10.1007\/978-3-642-31612-8_7"},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K.-I. Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K.-I., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Comb. Theory, Ser. B\u00a0102(2), 424\u2013435 (2012)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-I., Mohar, B., Reed, B.A.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: Proc. of FOCS 2008, pp. 771\u2013780 (2008)","DOI":"10.1109\/FOCS.2008.53"},{"issue":"3","key":"7_CR19","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/0222039","volume":"22","author":"L.M. Kirousis","year":"1993","unstructured":"Kirousis, L.M., Serna, M.J., Spirakis, P.G.: Parallel complexity of the connected subgraph problem. SIAM J. Comput.\u00a022(3), 573\u2013586 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02983372","volume":"28","author":"D.E. Knuth","year":"1990","unstructured":"Knuth, D.E.: Nested satisfiability. Acta Informatica\u00a028(1), 1\u20136 (1990)","journal-title":"Acta Informatica"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/BF01209713","volume":"30","author":"J. Kratochv\u00edl","year":"1993","unstructured":"Kratochv\u00edl, J., K\u0159iv\u00e1nek, M.: Satisfiability and co-nested formulas. Acta Inf.\u00a030, 397\u2013403 (1993)","journal-title":"Acta Inf."},{"issue":"3","key":"7_CR22","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"},{"issue":"1","key":"7_CR23","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J.\u00a051(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"issue":"3-4","key":"7_CR24","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1007\/s00453-010-9484-z","volume":"62","author":"D. Marx","year":"2012","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica\u00a062(3-4), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"7_CR25","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K. Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventheorie. Fundamenta Mathematicae\u00a010, 96\u2013115 (1927)","journal-title":"Fundamenta Mathematicae"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Mohar, B.: Embedding graphs in an arbitrary surface in linear time. In: Proc. of STOC 1996, pp. 392\u2013397 (1996)","DOI":"10.1145\/237814.237986"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"7_CR28","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: Proc. of SAT 2004, pp. 96\u2013103 (2004)"},{"issue":"7-8","key":"7_CR29","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 Inf.\u00a044(7-8), 509\u2013523 (2007)","journal-title":"Acta Inf."},{"issue":"8","key":"7_CR30","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed parameter tractable. J. Comput. Syst. Sci.\u00a075(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"7_CR31","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"1","key":"7_CR32","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":"2","key":"7_CR33","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory, Ser. B\u00a062(2), 323\u2013348 (1994)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"1","key":"7_CR34","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"},{"issue":"2","key":"7_CR35","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. Theor. Comput. Sci.\u00a08(2), 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"7_CR36","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebenen Komplexe. Mathematische Annalen\u00a0114(1), 570\u2013590 (1937)","journal-title":"Mathematische Annalen"},{"key":"7_CR37","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Proc. of IJCAI 2003, pp. 1173\u20131178 (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31612-8_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:40:28Z","timestamp":1620114028000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31612-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316111","9783642316128"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31612-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}