Improved algorithms for counting solutions in constraint satisfaction problems

DOI10.1007/B13743zbMATH Open1273.68330OpenAlexW2497660909MaRDI QIDQ5897192FDOQ5897192

Authors: Ola Angelsmark, Peter Jonsson 

Publication date: 2 March 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b13743

Recommendations

• Counting solutions to CSP using generating polynomials
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• 3-coloring in time
• scientific article; zbMATH DE number 2090009
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cited In (8)

• An enumerative algorithm for \#2SAT
• On two techniques of combining branching and treewidth
• Counting models for 2SAT and 3SAT formulae
• A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
• Counting solutions to CSP using generating polynomials
• Enumerating All Solutions for Constraint Satisfaction Problems
• Exact algorithms for counting 3-colorings of graphs
• 3-coloring in time

This page was built for publication: Improved algorithms for counting solutions in constraint satisfaction problems

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