liu.seSearch for publications in DiVA
Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Determining the Number of Solutions to Binary CSP Instances
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
2002 (English)In: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002, Heidelberg: Springer Verlag , 2002, p. 327-Conference paper, Published paper (Refereed)
##### Abstract [en]

Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge.

##### Place, publisher, year, edition, pages
Heidelberg: Springer Verlag , 2002. p. 327-
##### Keyword [en]
Tvärvetenskap, constraint satisfaction, counting problems, CSP
##### National Category
Computer Sciences
##### Identifiers
Local ID: 6788OAI: oai:DiVA.org:liu-24612DiVA, id: diva2:244934
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13

#### Open Access in DiVA

No full text in DiVA

#### Authority records BETA

Angelsmark, OlaJonsson, PeterLinusson, SvanteThapper, Johan

#### Search in DiVA

##### By author/editor
Angelsmark, OlaJonsson, PeterLinusson, SvanteThapper, Johan
##### By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science LaboratoryApplied Mathematics
##### On the subject
Computer Sciences

urn-nbn

#### Altmetric score

urn-nbn
Total: 85 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf