{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T22:43:03Z","timestamp":1768257783726,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540797227","type":"print"},{"value":"9783540797234","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79723-4_19","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T10:22:17Z","timestamp":1210069337000},"page":"202-213","source":"Crossref","is-referenced-by-count":26,"title":["A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances"],"prefix":"10.1007","author":[{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1\u20133","key":"19_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T. Brueggemann","year":"2004","unstructured":"Brueggemann, T., Kern, W.: An improved deterministic local search algorithm for 3-SAT. Theoretical Computer Science\u00a0329(1\u20133), 303\u2013313 (2004)","journal-title":"Theoretical Computer Science"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/3-540-45655-4_57","volume-title":"Computing and Combinatorics","author":"V. Dahll\u00f6f","year":"2002","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting satisfying assignments in 2-SAT and 3-SAT. In: H. Ibarra, O., Zhang, L. (eds.) COCOON 2002. LNCS, vol.\u00a02387, pp. 535\u2013543. Springer, Heidelberg (2002)"},{"issue":"1\u20133","key":"19_CR3","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V. Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2-SAT and 3-SAT formulae. Theoretical Computer Science\u00a0332(1\u20133), 265\u2013291 (2005)","journal-title":"Theoretical Computer Science"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(91)90315-S","volume":"81","author":"O. Dubois","year":"1991","unstructured":"Dubois, O.: Counting the number of solutions for instances of satisfiability. Theoretical Computer Science\u00a081, 49\u201364 (1991)","journal-title":"Theoretical Computer Science"},{"key":"19_CR5","unstructured":"Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proceedings of the 15th annual ACM-SIAM symposium on Discrete algorithms (SODA 2004), pp. 788\u2013797 (2004)"},{"key":"19_CR6","first-page":"47","volume":"87","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the EATCS\u00a087, 47\u201377 (2005)","journal-title":"Bulletin of the EATCS"},{"key":"19_CR7","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. Electronic Colloquium on Computational Complexity (ECCC)\u00a05(033) (2005)"},{"key":"19_CR8","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), p. 328 (2004)"},{"key":"19_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4400-4","volume-title":"The design and analysis of algorithms","author":"D. Kozen","year":"1992","unstructured":"Kozen, D.: The design and analysis of algorithms. Springer, New York (1992)"},{"key":"19_CR10","unstructured":"Littman, M., Pitassi, T., Impagliazzo, R.: On the complexity of counting satisfying assignments. In: The working notes of the LICS 2001 workshop on Satisfiability (2001)"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Ryser, H.J.: Combinatorial Mathematics. The Mathematical Association of America, Washington (1963)","DOI":"10.5948\/UPO9781614440147"},{"issue":"5","key":"19_CR12","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing\u00a020(5), 865\u2013877 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of enumeration and reliability problems. SIAM Journal of Computing\u00a08, 410\u2013421 (1979)","journal-title":"SIAM Journal of Computing"},{"key":"19_CR14","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, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/11561071_12","volume-title":"Algorithms \u2013 ESA 2005","author":"M. Wahlstr\u00f6m","year":"2005","unstructured":"Wahlstr\u00f6m, M.: An algorithm for the SAT problem for formulae of linear length. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 107\u2013118. Springer, Heidelberg (2005)"},{"key":"19_CR16","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures, and upper bounds for satisfiability and related problems. Link\u00f6ping Studies in Science and Technology, PhD Dissertation no. 1079 (2007), http:\/\/urn.kb.se\/resolve?urn=urn:nbn:se:liu:diva-8714"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(95)00144-1","volume":"155","author":"W. Zhang","year":"1996","unstructured":"Zhang, W.: Number of models and satisfiability of sets of clauses. Theoretical Computer Science\u00a0155, 277\u2013288 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79723-4_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:20:15Z","timestamp":1606184415000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79723-4_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797227","9783540797234"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79723-4_19","relation":{},"subject":[]}}