Some Study On SAT And Graph Coloring Algorithms

Constraint satisfaction problems(CSP) are basic problems in computer science for many years. And they have broad applications. In this thesis we discuss issues around these problems, especially propositional satisfiability(SAT) and graph coloring, and different solving algorithms of them - the new born SAT algorithm Survey Propagation(SP), a graph partitioning scheme Part for graph coloring and different symmetry breaking SAT algorithms X-Zchaff for graph coloring. Experiments results are provided.