{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T03:46:54Z","timestamp":1763092014602},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439967"},{"type":"electronic","value":"9783540456551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45655-4_57","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T07:37:01Z","timestamp":1179733021000},"page":"535-543","source":"Crossref","is-referenced-by-count":9,"title":["Counting Satisfying Assignments in 2-SAT and 3-SAT"],"prefix":"10.1007","author":[{"given":"Vilhelm","family":"Dahll\u00f6f","sequence":"first","affiliation":[]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"57_CR1","unstructured":"R. J. Bayardo, Jr. and J. Pehoushek. Counting models using connected components. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), pages 157\u2013162. AAAI Press, 2000."},{"key":"57_CR2","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1613\/jair.601","volume":"10","author":"E. Birnbaum","year":"1999","unstructured":"E. Birnbaum and E. L. Lozinskii. The good old Davis-Putnam procedure helps counting models. Journal of Artificial Intelligence Research, 10:457\u2013477, 1999.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"57_CR3","unstructured":"V. Dahll\u00f6f and P. Jonsson. An algorithm for counting maximum weighted independent sets and its applications. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2002), pages 292\u2013298, 2002."},{"issue":"1","key":"57_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(91)90315-S","volume":"81","author":"O. Dubois","year":"1991","unstructured":"O. Dubois. Counting the number of solutions for instances of satisfiability. Theoretical Computer Science, 81(1):49\u201364, 1991.","journal-title":"Theoretical Computer Science"},{"key":"57_CR5","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1112\/S1461157000000243","volume":"3","author":"L. Goldberg","year":"2000","unstructured":"L. Goldberg and M. Jerrum. Counting unlabelled subtrees of a tree is #P-complete. LMS Journal of Computation and Mathematics, 3:117\u2013124, 2000.","journal-title":"LMS Journal of Computation and Mathematics"},{"key":"57_CR6","volume-title":"Concrete Mathematics","author":"R. L. Graham","year":"1994","unstructured":"R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, Reading, MA, USA, second edition, 1994.","edition":"second edition"},{"issue":"1","key":"57_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/PL00001601","volume":"9","author":"C. S. Greenhill","year":"2000","unstructured":"C. S. Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity, 9(1):52\u201372, 2000.","journal-title":"Computational Complexity"},{"issue":"4","key":"57_CR8","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H. B. Hunt III","year":"1998","unstructured":"H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns. The complex-ity of planar counting problems. SIAM Journal on Computing, 27(4):1142\u20131167, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"D. Kozen. The design and analysis of algorithms. Springer-Verlag, 1992.","DOI":"10.1007\/978-1-4612-4400-4"},{"key":"57_CR10","unstructured":"M. L. Littman, T. Pitassi, and R. Impagliazzo. On the complexity of counting satisfying assignments. Unpublished manuscript."},{"issue":"1\u20132","key":"57_CR11","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"D. Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82(1\u20132):273\u2013302, 1996.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"57_CR12","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S. P. Vadhan","year":"2001","unstructured":"S. P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing, 31(2):398\u2013427, 2001.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"57_CR13","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"57_CR14","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(95)00144-1","volume":"155","author":"W. Zhang","year":"1996","unstructured":"W. Zhang. Number of models and satisfiability of sets of clauses. Theoretical Computer Science, 155(1):277\u2013288, 1996.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45655-4_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T16:14:25Z","timestamp":1550333665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45655-4_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439967","9783540456551"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45655-4_57","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}