{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:26:34Z","timestamp":1767860794458,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"7-8","license":[{"start":{"date-parts":[[2007,9,3]],"date-time":"2007-09-03T00:00:00Z","timestamp":1188777600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2007,11,9]]},"DOI":"10.1007\/s00236-007-0056-x","type":"journal-article","created":{"date-parts":[[2007,9,2]],"date-time":"2007-09-02T07:56:51Z","timestamp":1188719811000},"page":"509-523","source":"Crossref","is-referenced-by-count":26,"title":["Solving #SAT using vertex covers"],"prefix":"10.1007","volume":"44","author":[{"given":"Naomi","family":"Nishimura","sequence":"first","affiliation":[]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,3]]},"reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"Bacchus F., Dalmao S., Pitassi, T.: Algorithms and complexity results for #SAT and Bayesian inference. In: 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201903), pp. 340\u2013351 (2003)","DOI":"10.1109\/SFCS.2003.1238208"},{"issue":"1\u20132","key":"56_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender H.L. (1998). A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132): 1\u201345","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"56_CR3","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen J., Kanj I.A. and Jia W. (2001). Vertex cover: further observations and further improvements. J. Algorithms 41(2): 280\u2013301","journal-title":"J. Algorithms"},{"key":"56_CR4","doi-asserted-by":"crossref","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), pp. 238\u2013249 (2006)","DOI":"10.1007\/11821069_21"},{"issue":"1-2","key":"56_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle B., Makowsky J.A. and Rotics U. (2001). On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discr. Appl. Math. 108(1-2): 23\u201352","journal-title":"Discr. Appl. Math."},{"issue":"1\u20133","key":"56_CR6","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle B. and Olariu S. (2000). Upper bounds to the clique-width of graphs. Discr. Appl. Math. 101(1\u20133): 77\u2013114","journal-title":"Discr. Appl. Math."},{"key":"56_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"56_CR8","doi-asserted-by":"crossref","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.R.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discr. Appl. Math. to appear","DOI":"10.1016\/j.dam.2006.06.020"},{"issue":"4","key":"56_CR9","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"Flum J. and Grohe M. (2004). The parameterized complexity of counting problems. SIAM J. Comput. 33(4): 892\u2013922","journal-title":"SIAM J. Comput."},{"key":"56_CR10","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R. and Johnson D.R. (1979). Computers and Intractability. W.H. Freeman and Company, New York"},{"key":"56_CR11","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000) Selected papers from the Workshop on Graph-Theoretical Aspects of Computer Science (WG 99), Part 1 (Ascona)","DOI":"10.1142\/S0129054100000260"},{"issue":"1-2","key":"56_CR12","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0004-3702(02)00182-0","volume":"138","author":"G. Gottlob","year":"2002","unstructured":"Gottlob G., Scarcello F. and Sideri M. (2002). Fixed-parameter complexity in AI and nonmonotonic reasoning. Artif. Intell. 138(1-2): 55\u201386","journal-title":"Artif. Intell."},{"key":"56_CR13","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Szeider, S.: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems. Comput. J. Survey paper (2006, to appear)","DOI":"10.1093\/comjnl\/bxm056"},{"issue":"4","key":"56_CR14","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J. Gramm","year":"2005","unstructured":"Gramm J., Guo J., H\u00fcffner F. and Niedermeier R. (2005). Graph-modeled data clustering: fixed-parameter algorithms for clique generation. Theory Comput. Syst. 38(4): 373\u2013392","journal-title":"Theory Comput. Syst."},{"key":"56_CR15","unstructured":"Interian, Y.: Backdoor sets for random 3-SAT. In: Informal Proc. of SAT 2003 (Sixth International Conference on Theory and Applications of Satisfiability Testing, S. Margherita Ligure\u2014Portofino, Italy, 5\u20138 May 2003) pp. 231\u2013238 (2003)"},{"issue":"2","key":"56_CR16","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1137\/0218026","volume":"18","author":"K. Iwama","year":"1989","unstructured":"Iwama K. (1989). CNF-satisfiability test by counting and polynomial average time. SIAM J. Comput. 18(2): 385\u2013391","journal-title":"SIAM J. Comput."},{"key":"56_CR17","unstructured":"Kilby, P., Slaney, J.K., Thi\u00e9baux, S., Walsh, T.: Backbones and backdoors in satisfiability. In: Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, 9\u201313 July 2005. AAAI, Pittsburgh, pp. 1368\u20131373 (2005)"},{"key":"56_CR18","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, North-Holland (2001)","DOI":"10.1016\/S1571-0653(04)00313-0"},{"key":"56_CR19","doi-asserted-by":"crossref","unstructured":"Lynce, I., Marques-Silva, J.P.: Hidden structure in unsatisfiable random 3-SAT: An empirical study. In: 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), 15-17 November 2004, Boca Raton, FL, USA, pp 246\u2013251. IEEE Computer Society, (2004)","DOI":"10.1109\/ICTAI.2004.68"},{"key":"56_CR20","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms: Oxford Lecture Series in Mathematics and its Applications","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier R. (2006). Invitation to Fixed-Parameter Algorithms: Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, New York"},{"key":"56_CR21","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: Proceedings of SAT 2004 (Seventh International Conference on Theory and Applications of Satisfiability Testing, 10\u201313 May 2004. Vancouver, Canada, pp. 96\u2013103 (2004)"},{"issue":"4","key":"56_CR22","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S. Oum","year":"2006","unstructured":"Oum S. and Seymour P. (2006). Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96(4): 514\u2013528","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1\u20132","key":"56_CR23","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth D. (1996). On the hardness of approximate reasoning. Artif. Intell. 82(1\u20132): 273\u2013302","journal-title":"Artif. Intell."},{"key":"56_CR24","unstructured":"Ruan, Y., Kautz, H.A., Horvitz, E.: The backdoor key: a path to understanding problem hardness. In: McGuinness D.L., Ferguson G. (eds.) Proceedings of the 19th National Conference on Artificial Intelligence, 16th Conference on Innovative Applications of Artificial Intelligence, pp. 124\u2013130. AAAI Press\/The MIT Press, Pittsburgh\/Cambridge (2004)"},{"key":"56_CR25","doi-asserted-by":"crossref","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. In: Proceedings of LPAR 2007, 14th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Yerevan, Armenia, 15\u201319 October 2007. Lecture Notes in Computer Science (2007, to appear)","DOI":"10.1007\/978-3-540-75560-9_35"},{"key":"56_CR26","doi-asserted-by":"crossref","unstructured":"Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia E., Tacchella A. (eds.) Theory and Applications of Satisfiability, 6th International Conference, SAT 2003, Selected and Revised Papers. Lecture Notes in Computer Science, vol. 2919, pp. 188\u2013202. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-24605-3_15"},{"key":"56_CR27","unstructured":"Szeider, S.: Backdoor sets for DLL subsolvers. J. Autom. Reason. 35(1\u20133), 73\u201388 (2005). Reprinted as Chap. 4 of the book SAT 2005\u2014Satisfiability Research in the Year 2005, Giunchiglia E., Walsh T. (eds.) Springer, Heidelberg (2006)"},{"issue":"2","key":"56_CR28","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant L.G. (1979). The complexity of computing the permanent. Theor. Comput. Sci. 8(2): 189\u2013201","journal-title":"Theor. Comput. Sci."},{"key":"56_CR29","unstructured":"Williams, R., Gomes, C., Selman, B.: On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In: Informal Proc. of SAT 2003 (Sixth International Conference on Theory and Applications of Satisfiability Testing, Margherita S. Ligure\u2014Portofino, Italy, 5\u20138 May 2003), pp. 222\u2013230 (2003)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0056-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-007-0056-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0056-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T00:08:48Z","timestamp":1684022928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-007-0056-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,3]]},"references-count":29,"journal-issue":{"issue":"7-8","published-print":{"date-parts":[[2007,11,9]]}},"alternative-id":["56"],"URL":"https:\/\/doi.org\/10.1007\/s00236-007-0056-x","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,3]]}}}