{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:52:40Z","timestamp":1744217560869,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319662626"},{"type":"electronic","value":"9783319662633"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-66263-3_2","type":"book-chapter","created":{"date-parts":[[2017,8,8]],"date-time":"2017-08-08T04:05:11Z","timestamp":1502165111000},"page":"20-37","source":"Crossref","is-referenced-by-count":4,"title":["Backdoor Treewidth for SAT"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,9]]},"reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/BFb0017382","volume-title":"Graph Grammars and Their Application to Computer Science","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D.: An algebraic theory of graph reduction. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol. 532, pp. 70\u201383. Springer, Heidelberg (1991). doi: 10.1007\/BFb0017382"},{"key":"2_CR2","series-title":"Frontiers in Artificial Intelligence and Applications","volume-title":"Handbook of Satisfiability","year":"2009","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009)"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/3-540-61332-3_153","volume-title":"Computing and Combinatorics","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Fluiter, B.: Reduction algorithms for constructing solutions in graphs with small treewidth. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol. 1090, pp. 199\u2013208. Springer, Heidelberg (1996). doi: 10.1007\/3-540-61332-3_153"},{"issue":"2","key":"2_CR4","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"HL Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Inf. Comput. 167(2), 86\u2013119 (2001)","journal-title":"Inf. Comput."},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/3-540-60084-1_80","volume-title":"Automata, Languages and Programming","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. In: F\u00fcl\u00f6p, Z., G\u00e9cseg, F. (eds.) ICALP 1995. LNCS, vol. 944, pp. 268\u2013279. Springer, Heidelberg (1995). doi: 10.1007\/3-540-60084-1_80"},{"issue":"1","key":"2_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(94)90033-7","volume":"55","author":"E Boros","year":"1994","unstructured":"Boros, E., Hammer, P.L., Sun, X.: Recognition of $$q$$ -Horn formulae in linear time. Discr. Appl. Math. 55(1), 1\u201313 (1994)","journal-title":"Discr. Appl. Math."},{"key":"2_CR7","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009). http:\/\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3"},{"key":"2_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). doi: 10.1007\/978-3-319-21275-3"},{"key":"2_CR9","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012). doi: 10.1007\/978-3-662-53622-3","edition":"4"},{"key":"2_CR10","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). doi: 10.1007\/978-1-4471-5559-1"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations (extended abstract). In: FOCS, pp. 520\u2013525 (1989)","DOI":"10.1109\/SFCS.1989.63528"},{"key":"2_CR12","unstructured":"de Fluiter, B.: Algorithms for graphs of small treewidth. Ph.D. thesis, Utrecht University (1997)"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Ramanujan, M.S., Saurabh, S.: Solving d-SAT via backdoors to small treewidth. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, pp. 630\u2013641, 4\u20136 January 2015 (2015)","DOI":"10.1137\/1.9781611973730.43"},{"key":"2_CR14","unstructured":"Ganian, R., Ramanujan, M.S., Szeider, S.: Combining treewidth and backdoors for CSP. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 66, pp. 36:1\u201336:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"2","key":"2_CR15","doi-asserted-by":"crossref","first-page":"29:1","DOI":"10.1145\/3014587","volume":"13","author":"R Ganian","year":"2017","unstructured":"Ganian, R., Ramanujan, M.S., Szeider, S.: Discovering archipelagos of tractability for constraint satisfaction and counting. ACM Trans. Algorithms 13(2), 29:1\u201329:32 (2017). http:\/\/doi.acm.org\/10.1145\/3014587","journal-title":"ACM Trans. Algorithms"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-642-30891-8_15","volume-title":"The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Szeider, S.: Backdoors to satisfaction. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 287\u2013317. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-30891-8_15"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, pp. 479\u2013488, 6\u20138 June 2011","DOI":"10.1145\/1993636.1993700"},{"issue":"6","key":"2_CR18","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient algorithms for graph manipulation [H] (algorithm 447). Commun. ACM 16(6), 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"key":"2_CR19","series-title":"Frontiers in Artificial Intelligence and Applications","first-page":"339","volume-title":"Handbook of Satisfiability","author":"H Kleine B\u00fcning","year":"2009","unstructured":"Kleine B\u00fcning, H., Kullmann, O.: Minimal unsatisfiability and autarkies, Chap. 11. In: Biere, A., Heule, M.J.H., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 339\u2013401. IOS Press, Amsterdam (2009)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Kleine B\u00fcning, H., Zhao, X.: Satisfiable formulas closed under replacement. In: Kautz, H., Selman, B. (eds.) Proceedings for the Workshop on Theory and Applications of Satisfiability. Electronic Notes in Discrete Mathematics, vol. 9. Elsevier Science Publishers, North-Holland (2001)","DOI":"10.1016\/S1571-0653(04)00313-0"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","year":"1994","unstructured":"Kloks, T. (ed.): Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994). doi: 10.1007\/BFb0045375"},{"key":"2_CR22","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: Proceedings of Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada, pp. 96\u2013103, 10\u201313 May 2004"},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2012.12.039","volume":"481","author":"S Ordyniak","year":"2013","unstructured":"Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic CNF formulas. Theor. Comput. Sci. 481, 85\u201399 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"2_CR24","doi-asserted-by":"crossref","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 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"2_CR25","first-page":"425","volume-title":"Handbook of Satisfiability","author":"M Samer","year":"2009","unstructured":"Samer, M., Szeider, S.: Fixed-parameter tractability, Chap. 13. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, pp. 425\u2013454. IOS Press, Amsterdam (2009)"},{"issue":"1","key":"2_CR26","doi-asserted-by":"crossref","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 8(1), 50\u201364 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"2_CR27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.jcss.2009.04.003","volume":"76","author":"M Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2), 103\u2013114 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR28","unstructured":"Williams, R., Gomes, C., Selman, B.: On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In: Informal Proceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT 2003), S. Margherita Ligure - Portofino, Italy, pp. 222\u2013230, 5\u20138 May 2003"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2017"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66263-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T23:35:36Z","timestamp":1569972936000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66263-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319662626","9783319662633"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66263-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}