{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:57:35Z","timestamp":1759683455355},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755586"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75560-9_35","type":"book-chapter","created":{"date-parts":[[2007,10,6]],"date-time":"2007-10-06T01:36:46Z","timestamp":1191634606000},"page":"484-498","source":"Crossref","is-referenced-by-count":11,"title":["Algorithms for Propositional Model Counting"],"prefix":"10.1007","author":[{"given":"Marko","family":"Samer","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","first-page":"1","volume-title":"The Design and Analysis of Computer Algorithms chapter 1, Models of computation","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms chapter 1, Models of computation, pp. 1\u201341. Addison-Wesley, Reading (1974)"},{"issue":"3-4","key":"35_CR2","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s004530010025","volume":"27","author":"B. Aspvall","year":"2000","unstructured":"Aspvall, B., Proskurowski, A., Telle, J.A.: Memory requirements for table computations in partial k-tree algorithms. Algorithmica\u00a027(3-4), 382\u2013394 (2000)","journal-title":"Algorithmica"},{"key":"35_CR3","first-page":"340","volume-title":"FOCS 2003","author":"F. Bacchus","year":"2003","unstructured":"Bacchus, F., Dalmao, S., Pitassi, T.: Algorithms and complexity results for #SAT and Bayesian inference. In: FOCS 2003, pp. 340\u2013351. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"35_CR4","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"issue":"6","key":"35_CR5","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 Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"35_CR6","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: Vojt\u00e1\u0161, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 1\u201316. Springer, Heidelberg (2005)"},{"key":"35_CR7","unstructured":"Cohen, D., Jeavons, P., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In: IJCAI 2005, pp. 72\u201377. Professional Book Center (2005)"},{"issue":"2","key":"35_CR8","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 of Computing Systems\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"1-2","key":"35_CR9","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. Discrete Applied Mathematics\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"35_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"35_CR11","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. Discrete Applied Mathematics (in press)","DOI":"10.1016\/j.dam.2006.06.020"},{"key":"35_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"35_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/1250790.1250800","volume-title":"STOC 2007","author":"M. F\u00fcrer","year":"2007","unstructured":"F\u00fcrer, M.: Faster integer multiplication. In: STOC 2007, pp. 57\u201366. ACM Press, New York (2007)"},{"issue":"3","key":"35_CR14","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. Journal of Computer and System Sciences\u00a064(3), 579\u2013627 (2002)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1-2","key":"35_CR15","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":"35_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/1109557.1109590","volume-title":"SODA 2006","author":"M. Grohe","year":"2006","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: SODA 2006, pp. 289\u2013298. ACM Press, New York (2006)"},{"key":"35_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Springer, Heidelberg (1994)"},{"key":"35_CR18","first-page":"294","volume-title":"Seminumerical Algorithms, chapter 4.3.3 How fast can we multiply?","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming. In: Seminumerical Algorithms, chapter 4.3.3 How fast can we multiply? 3rd edn., vol.\u00a02, pp. 294\u2013318. Addison-Wesley, Reading (1998)","edition":"3"},{"issue":"2","key":"35_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences\u00a061(2), 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics 8 (2001)","DOI":"10.1016\/S1571-0653(05)80078-2"},{"key":"35_CR21","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"35_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11814948_36","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"N. Nishimura","year":"2006","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Solving #SAT using vertex covers. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 396\u2013409. Springer, Heidelberg (2006)"},{"issue":"4","key":"35_CR23","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S. Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B\u00a096(4), 514\u2013528 (2006)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"35_CR24","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\u00a0X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B\u00a052(2), 153\u2013190 (1991)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1-2","key":"35_CR25","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":"35_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/11889205_36","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"M. Samer","year":"2006","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 499\u2013513. Springer, Heidelberg (2006)"},{"key":"35_CR27","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation ganzer Zahlen. Computing\u00a07, 281\u2013292 (1971)","journal-title":"Computing"},{"issue":"2","key":"35_CR28","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":"35_CR29","first-page":"81","volume-title":"VLDB 1981","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: VLDB 1981, pp. 81\u201394. IEEE Computer Society Press, Los Alamitos (1981)"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming, Artificial Intelligence, and Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75560-9_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:24:46Z","timestamp":1619504686000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75560-9_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755586"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75560-9_35","relation":{},"subject":[]}}