Improved algorithms for counting solutions in constraint satisfaction problems

DOI10.1007/B13743MaRDI QIDQ5897192zbMATH OpenOpenAlexFDO

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

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)

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.

Cited in

(8)

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

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)