liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
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, 327- p.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. 327- p.
Keyword [en]
Tvärvetenskap, constraint satisfaction, counting problems, CSP
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-24612Local ID: 6788OAI: oai:DiVA.org:liu-24612DiVA: diva2:244934
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2017-02-23

Open Access in DiVA

No full text

Other links

http://www.springerlink.com/link.asp?id=v08ecxt18r9al6v2

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
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 67 hits
CiteExportLink to record
Permanent link

Direct link
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