{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T15:18:43Z","timestamp":1782400723258,"version":"3.54.5"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319092836","type":"print"},{"value":"9783319092843","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09284-3_3","type":"book-chapter","created":{"date-parts":[[2014,7,2]],"date-time":"2014-07-02T09:43:21Z","timestamp":1404294201000},"page":"16-31","source":"Crossref","is-referenced-by-count":3,"title":["Solving MaxSAT and #SAT on Structured CNF Formulas"],"prefix":"10.1007","author":[{"given":"Sigve Hortemo","family":"S\u00e6ther","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Vatshelle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Bacchus, F., Dalmao, S., Pitassi, T.: Algorithms and complexity results for# sat and bayesian inference. In: Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 340\u2013351. IEEE (2003)","DOI":"10.1109\/SFCS.2003.1238208"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R. Belmonte","year":"2013","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci.\u00a0511, 54\u201365 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey, Monographs on Discrete Mathematics and Applications","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, Monographs on Discrete Mathematics and Applications, vol.\u00a03. SIAM Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"3_CR4","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars. Comb.\u00a067 (2003)"},{"issue":"7","key":"3_CR5","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1016\/j.dam.2009.09.009","volume":"158","author":"B.M. Bui-Xuan","year":"2010","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Applied Mathematics\u00a0158(7), 809\u2013819 (2010)","journal-title":"Discrete Applied Mathematics"},{"issue":"39","key":"3_CR6","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"B.M. Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoretical Computer Science\u00a0412(39), 5187\u20135204 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0012-365X(03)00303-0","volume":"276","author":"B. Courcelle","year":"2004","unstructured":"Courcelle, B.: Clique-width of countable graphs: a compactness property. Discrete Mathematics\u00a0276(1-3), 127\u2013148 (2004)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0004-3702(00)00069-2","volume":"126","author":"A. Darwiche","year":"2001","unstructured":"Darwiche, A.: Recursive conditioning. Artificial Intelligence\u00a0126(1), 5\u201341 (2001)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"3_CR9","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.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics\u00a0156(4), 511\u2013529 (2008)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"3_CR10","doi-asserted-by":"crossref","first-page":"59","DOI":"10.3233\/FI-2013-800","volume":"123","author":"R. Ganian","year":"2013","unstructured":"Ganian, R., Hlinen\u00fd, P., Obdrz\u00e1lek, J.: Better algorithms for satisfiability problems for formulas of bounded rank-width. Fundam. Inform.\u00a0123(1), 59\u201376 (2013)","journal-title":"Fundam. Inform."},{"key":"3_CR11","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)"},{"issue":"2","key":"3_CR12","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/jctb.2001.2082","volume":"84","author":"J.F. Geelen","year":"2002","unstructured":"Geelen, J.F., Gerards, B., Whittle, G.: Branch-width and well-quasi-ordering in matroids and graphs. J. Combin. Theory Ser. B\u00a084(2), 270\u2013290 (2002)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20006","volume":"46","author":"P. Hell","year":"2004","unstructured":"Hell, P., Huang, J.: Interval bigraphs and circular arc graphs. Journal of Graph Theory\u00a046(4), 313\u2013327 (2004)","journal-title":"Journal of Graph Theory"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-28050-4_18","volume-title":"Parameterized and Exact Computation","author":"E.M. Hvidevold","year":"2012","unstructured":"Hvidevold, E.M., Sharmin, S., Telle, J.A., Vatshelle, M.: Finding good decompositions for dynamic programming on dense graphs. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 219\u2013231. Springer, Heidelberg (2012)"},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(87)90028-7","volume":"26","author":"B. Jaumard","year":"1987","unstructured":"Jaumard, B., Simeone, B.: On the complexity of the maximum satisfiability problem for horn formulas. Inf. Process. Lett.\u00a026(1), 1\u20134 (1987)","journal-title":"Inf. Process. Lett."},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-33293-7_15","volume-title":"Parameterized and Exact Computation","author":"P. Kaski","year":"2012","unstructured":"Kaski, P., Koivisto, M., Nederlof, J.: Homomorphic hashing for sparse coefficient extraction. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol.\u00a07535, pp. 147\u2013158. Springer, Heidelberg (2012)"},{"issue":"1-3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0166-218X(97)00027-9","volume":"78","author":"H. M\u00fcller","year":"1997","unstructured":"M\u00fcller, H.: Recognizing interval digraphs and interval bigraphs in polynomial time. Discrete Applied Mathematics\u00a078(1-3), 189\u2013205 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR18","unstructured":"Paulusma, D., Slivovsky, F., Szeider, S.: Model counting for CNF formulas of bounded modular treewidth. In: Portier, N., Wilke, T. (eds.) STACS. LIPIcs, vol.\u00a020, pp. 55\u201366. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"3_CR19","unstructured":"Rafiey, A.: Recognizing interval bigraphs by forbidden patterns. CoRR abs\/1211.2662 (2012)"},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V. Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified NP-complete MAXSAT problem. Inf. Process. Lett.\u00a065(1), 1\u20136 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"3_CR21","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"},{"key":"3_CR22","unstructured":"Roth, D.: A connectionist framework for reasoning: Reasoning with examples. In: Clancey, W.J., Weld, D.S. (eds.) AAAI\/IAAI, vol.\u00a02, pp. 1256\u20131261. AAAI Press \/ The MIT Press (1996)"},{"issue":"1","key":"3_CR23","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"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Slivovsky, F., Szeider, S.: Model counting for formulas of bounded clique-width. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC2013. LNCS, vol.\u00a08283, pp. 677\u2013687. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-45030-3_63"},{"key":"3_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":"3_CR26","unstructured":"Vatshelle, M.: New width parameters of graphs. Ph.D. thesis. The University of Bergen (2012)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09284-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T16:52:10Z","timestamp":1746291130000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09284-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319092836","9783319092843"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09284-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}