Counting solutions to CSP using generating polynomials

DOI10.1016/J.JDA.2014.01.004MaRDI QIDQ2447541zbMATH OpenOpenAlexFDO

Authors Daniel Berend, Shahar Golan

Publication date 28 April 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2014.01.004

zbMATH Keywords

CNF SATconstraint satisfaction problemcounting problemgenerating functionstreewidth

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved algorithms for counting solutions in constraint satisfaction problems
• Complexity of the counting constraint satisfaction problem
• scientific article; zbMATH DE number 4162262
• The Complexity of the Counting Constraint Satisfaction Problem
• The complexity of the counting constraint satisfaction problem

Cites work

• Algorithms for Propositional Model Counting
• Conjunctive-query containment and constraint satisfaction
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3709576 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1859215 (Why is no real title available?)
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Optimal 2-constraint satisfaction via sum-product algorithms
• Treewidth. Computations and approximations

Cited in

(6)

• Finding and counting permutations via CSPs
• Polynomial algorithm for solving cross-matching puzzles
• scientific article; zbMATH DE number 4162262 (Why is no real title available?)
• Revisiting counting solutions for the global cardinality constraint
• Counting Models in Integer Domains
• Improved algorithms for counting solutions in constraint satisfaction problems

This page was built for publication: Counting solutions to CSP using generating polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2447541)