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

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

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)

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

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)