Counting Constraint Satisfaction Problems

Author Mark Jerrum



PDF
Thumbnail PDF

File

DFU.Vol7.15301.205.pdf
  • Filesize: 0.61 MB
  • 27 pages

Document Identifiers

Author Details

Mark Jerrum

Cite AsGet BibTex

Mark Jerrum. Counting Constraint Satisfaction Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 205-231, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/DFU.Vol7.15301.205

Abstract

This chapter surveys counting Constraint Satisfaction Problems (counting CSPs, or #CSPs) and their computational complexity. It aims to provide an introduction to the main concepts and techniques, and present a representative selection of results and open problems. It does not cover holants, which are the subject of a separate chapter.
Keywords
  • Approximation algorithms
  • Computational complexity
  • Constraint satisfaction problems
  • Counting problems
  • Partition functions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail