Another Look at Graph Coloring via Propositional Satisfiability

Van Gelder, Allen

To appear at Computational Symposium on Graph Coloring and Generalizations (COLOR02), Ithaca, NY, 7-8 September 2002

Abstract

This paper will study the solution of graph coloring problems by encoding into propositional satisfiability problems. The study will cover three kinds of satisfiability solvers, based on postorder reasoning (e.g., grasp, chaff), preorder reasoning (e.g., 2cl, 2clsEq), and back-chaining (modoc). The study will evaluate at least three encodings, one of them believed to be new. The study will also consider some simple symmetry-breaking methods, specific to coloring. Preliminary results are given. If time permits, variations of graph coloring will be considered.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Maintainer trick@cmu.edu.
Start Conference Manager
Conference Systems