{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:03:54Z","timestamp":1725483834892},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441205"},{"type":"electronic","value":"9783540461357"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46135-3_22","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T05:59:47Z","timestamp":1179208787000},"page":"327-340","source":"Crossref","is-referenced-by-count":1,"title":["Determining the Number of Solutions to Binary CSP Instances"],"prefix":"10.1007","author":[{"given":"Ola","family":"Angelsmark","sequence":"first","affiliation":[]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[]},{"given":"Svante","family":"Linusson","sequence":"additional","affiliation":[]},{"given":"Johan","family":"Thapper","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"B. Aspvall, M. F. Plass, and R. E. Tarjan. A linear time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters, 8:121\u2013123, 1979.","journal-title":"Information Processing Letters"},{"unstructured":"R. Bayardo and J. D. Pehoushek. Counting models using connected components. In Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence (AAAI\/IAAI-2000), pages 157\u2013162, 2000.","key":"22_CR2"},{"issue":"2","key":"22_CR3","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","volume":"65","author":"M. Cooper","year":"1994","unstructured":"M. Cooper, D. A. Cohen, and P. G. Jeavons. Characterising tractable constraints. Artificial Intelligence, 65(2):347\u2013361, 1994.","journal-title":"Artificial Intelligence"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"N. Creignou and M. Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125:1\u201312, 1996.","journal-title":"Information and Computation"},{"unstructured":"V. Dahll\u00f6f and P. Jonsson. An algorithm for counting maximum weighted independent sets and its applications. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2002), pages 292\u2013298, 2002.","key":"22_CR5"},{"doi-asserted-by":"crossref","unstructured":"V. Dahll\u00f6f, P. Jonsson, and M. Wahlstr\u00f6m. Counting satisfying assignments in 2-SAT and 3-SAT. In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON-2002), Singapore, Aug. 2002. To appear.","key":"22_CR6","DOI":"10.1007\/3-540-45655-4_57"},{"issue":"1","key":"22_CR7","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":"22_CR8","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M. Dyer","year":"2000","unstructured":"M. Dyer and C. Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17:260\u2013289, 2000.","journal-title":"Random Structures and Algorithms"},{"unstructured":"D. Eppstein. Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA-2001), pages 329\u2013337, 2001.","key":"22_CR9"},{"unstructured":"T. Feder and R. Motwani. Worst-case time bounds for coloring and satisfiability problems. Unpublished manuscript.","key":"22_CR10"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1023\/A:1018941030227","volume":"24","author":"P. G. Jeavons","year":"1998","unstructured":"P. G. Jeavons, D. A. Cohen, and J. K. Pearson. Constraints and universal algebra. Annals of Mathematics and Artificial Intelligence, 24:51\u201367, 1998.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M. Jerrum","year":"1995","unstructured":"M. Jerrum. A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Structures and Algorithms, 7:157\u2013165, 1995.","journal-title":"Random Structures and Algorithms"},{"unstructured":"V. Kumar. Algorithms for constraint-satisfaction problems: A survey. AI Magazine, pages 32\u201344, Spring, 1992.","key":"22_CR13"},{"unstructured":"M. L. Littman, T. Pitassi, and R. Impagliazzo. On the complexity of counting satisfying assignments. Unpublished manuscript, 2001.","key":"22_CR14"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A. K. Mackworth","year":"1977","unstructured":"A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99\u2013118, 1977.","journal-title":"Artificial Intelligence"},{"doi-asserted-by":"crossref","unstructured":"S. Micali and V. V. Vazirani. v \u00b7 e ) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (FOCS-1980), pages 10\u201316. IEEE Computer Society, 1980.","key":"22_CR16","DOI":"10.1109\/SFCS.1980.12"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7:95\u2013132, 1974.","journal-title":"Information Sciences"},{"unstructured":"J. K. Pearson and P. G. Jeavons. A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway, University of London, July 1997.","key":"22_CR18"},{"key":"22_CR19","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:273\u2013302, 1996.","journal-title":"Artificial Intelligence"},{"doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In 40th Annual Symposium on Foundations of Computer Science (FOCS-1999), pages 410\u2013414. IEEE Computer Society, 1999.","key":"22_CR20","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"2","key":"22_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"22_CR22","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"E. Vigoda. Improved bounds for sampling colorings. In 40th Annual Symposium on Foundations of Computer Science (FOCS-1999), pages 51\u201359. IEEE Computer Society, 1999.","key":"22_CR23","DOI":"10.1109\/SFFCS.1999.814577"},{"issue":"1","key":"22_CR24","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","Principles and Practice of Constraint Programming - CP 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46135-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T16:59:14Z","timestamp":1550336354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46135-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441205","9783540461357"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46135-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}