Counting solutions to CSP using generating polynomials

DOI10.1016/J.JDA.2014.01.004zbMATH Open1298.68106OpenAlexW2020624521MaRDI QIDQ2447541FDOQ2447541

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

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

zbMATH Keywords

treewidthgenerating functionsconstraint satisfaction problemcounting problemCNF SAT

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Conjunctive-query containment and constraint satisfaction
• Graph minors. II. Algorithmic aspects of tree-width
• Treewidth. Computations and approximations
• Graph minors. I. Excluding a forest
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Optimal 2-constraint satisfaction via sum-product algorithms
• Title not available (Why is that?)
• Algorithms for Propositional Model Counting
• Title not available (Why is that?)

Cited In (6)

• Polynomial algorithm for solving cross-matching puzzles
• Finding and counting permutations via CSPs
• Improved algorithms for counting solutions in constraint satisfaction problems
• Title not available (Why is that?)
• Revisiting counting solutions for the global cardinality constraint
• Counting Models in Integer Domains

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)