{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:29:28Z","timestamp":1725542968555},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540372066"},{"type":"electronic","value":"9783540372073"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11814948_36","type":"book-chapter","created":{"date-parts":[[2006,7,18]],"date-time":"2006-07-18T10:12:38Z","timestamp":1153217558000},"page":"396-409","source":"Crossref","is-referenced-by-count":6,"title":["Solving #SAT Using Vertex Covers"],"prefix":"10.1007","author":[{"given":"Naomi","family":"Nishimura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_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 2003), pp. 340\u2013351 (2003)","DOI":"10.1109\/SFCS.2003.1238208"},{"issue":"1-2","key":"36_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci.\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"36_CR3","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Simplicity is beauty: Improved upper bounds for vertex cover. Technical Report TR05-008, DePaul University, Chicago IL (2005)"},{"issue":"2","key":"36_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst.\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1-2","key":"36_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discr. Appl. Math.\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discr. Appl. Math."},{"issue":"1-3","key":"36_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discr. Appl. Math.\u00a0101(1-3), 77\u2013114 (2000)","journal-title":"Discr. Appl. Math."},{"key":"36_CR7","volume-title":"Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. In: Monographs in Computer Science, Springer, Heidelberg (1999)"},{"key":"36_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":"36_CR9","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput.\u00a033(4), 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"36_CR10","first-page":"423","volume":"11","author":"M.C. Golumbic","year":"1999","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. WG 1999\u00a011(3), 423\u2013443 (2000), Selected papers from the Workshop on Graph-Theoretical Aspects of Computer Science (WG 1999), Part 1 (Ascona)","journal-title":"WG"},{"issue":"4","key":"36_CR11","doi-asserted-by":"publisher","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., Niedermeier, R.: Graph-modeled data clustering: fixed-parameter algorithms for clique generation. Theory Comput. Syst.\u00a038(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"1-2","key":"36_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0004-3702(02)00182-0","volume":"138","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Scarcello, F., Sideri, M.: Fixed-parameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence\u00a0138(1-2), 55\u201386 (2002)","journal-title":"Artificial Intelligence"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Szeider, S.: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems (April 2006) (submitted)","DOI":"10.1093\/comjnl\/bxm056"},{"key":"36_CR14","unstructured":"Interian, Y.: Backdoor sets for random 3-SAT. In: Informal Proceedings of SAT 2003, pp. 231\u2013238 (2003)"},{"issue":"2","key":"36_CR15","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1137\/0218026","volume":"18","author":"K. Iwama","year":"1989","unstructured":"Iwama, K.: CNF-satisfiability test by counting and polynomial average time. SIAM J. Comput.\u00a018(2), 385\u2013391 (1989)","journal-title":"SIAM J. Comput."},{"key":"36_CR16","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 (AAAI 2005), pp. 1368\u20131373 (2005)"},{"key":"36_CR17","series-title":"Electronic Notes in Discrete Mathematics","volume-title":"Proceedings for the Workshop on Theory and Applications of Satisfiability","author":"H. Kleine B\u00fcning","year":"2001","unstructured":"Kleine B\u00fcning, H., Zhao, X.: Satisfiable formulas closed under replacement. In: Proceedings for the Workshop on Theory and Applications of Satisfiability. Electronic Notes in Discrete Mathematics, vol.\u00a09, Elsevier Science Publishers, North-Holland (2001)"},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1109\/ICTAI.2004.68","volume-title":"16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004)","author":"I. Lynce","year":"2004","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), pp. 246\u2013251. IEEE Computer Society, Los Alamitos (2004)"},{"key":"36_CR19","volume-title":"Oxford Lecture Series in Mathematics and Its Applications","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. In: Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, Oxford (2006)"},{"key":"36_CR20","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: Informal Proceedings of SAT 2004, pp. 96\u2013103 (2004)"},{"key":"36_CR21","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory, Ser. B (to appear)"},{"issue":"2","key":"36_CR22","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1-2","key":"36_CR23","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. Artificial Intelligence\u00a082(1-2), 273\u2013302 (1996)","journal-title":"Artificial Intelligence"},{"key":"36_CR24","unstructured":"Ruan, Y., Kautz, H.A., Horvitz, E.: The backdoor key: A path to understanding problem hardness. In: 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 (2004)"},{"key":"36_CR25","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)"},{"key":"36_CR26","doi-asserted-by":"crossref","unstructured":"Szeider, S.: Backdoor sets for DLL subsolvers. Journal of Automated Reasoning (in press, 2005)","DOI":"10.1007\/s10817-005-9007-9"},{"issue":"2","key":"36_CR27","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. Theoret. Comput. Sci.\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"key":"36_CR28","unstructured":"Williams, R., Gomes, C., Selman, B.: On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In: Informal Proceedings of SAT 2003, pp. 222\u2013230 (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11814948_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:28:04Z","timestamp":1619508484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11814948_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540372066","9783540372073"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11814948_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}