SAT: references on satisfiability

collected by Ian P. Gent
Toby Walsh

Local search methods


A New Method for Solving Hard Satisfiability Problems
Bart Selman, Hector Levesque and David Mitchell, Proceedings AAAI-92.

An Empirical Analysis of Search in GSAT.
Ian Gent and Toby Walsh, Journal of Artificial Intelligence Research, Vol. 1, September 1993.

GenSAT (including HSAT)

Towards an Understanding of Hill-climbing Procedures for SAT
Ian Gent and Toby Walsh. Proceedings of AAAI-93.


An Empirical Study of Greedy Local Search for Satisfiability Testing
Bart Selman and Henry Kautz, Proc. AAAI-93.

Weighting for Godot: Learning heuristics for GSAT
J. Frank, Proc. AAAI-96.

Random Walk

Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems
Bart Selman and Henry Kautz, Proc. IJCAI-93.

Unsatisfied Variables in Local Search
Ian Gent and Toby Walsh. in `Hybrid Problems, Hybrid Solutions', ed. J. Hallam, IOS Press, Amsterdam, 1995, pages 73-85. (Proceedings of AISB-95.)


Local Search Strategies for Satisfiability Testing
Bart Selman, Henry Kautz and Bram Cohen, Proceedings of 2nd DIMACS Challenge on Cliques, Coloring and Satisfiability.


Evidence for Invariants in Local Search
David McAllester, Bart Selman, and Henry Kautz. Proc. AAAI-97, Providence, RI, 1997.

The greedy algorithm

On the Stupid Algorithm for Satisfiability
Ian Gent. Technical report, APES-03-1998, April 1998.