next up previous
Next: About this document ...

A WebPage on SAT algorithms

by William Gasarch

(For now this is just papers and talks that I want to gather in one place)

  1. Compact talk on 3-SAt and MIS TALK.PDF

  2. 2-SAT in P and MAX 2-SAT NPC. Slides by Muli Safra. 2SAT.PPT.

  3. Algorithms for 3-SAT. A talk by Bill Gasarch based on the literature as presented in the AWESOME book The Satisfiability Problem SAT, Algorithms and Analyzes by Uwe Schoning and Jacob. SATTALK.PDF.

  4. Backdoor Variables and other approaches to SAT. A talk by Marco Gario. SATBACK.PDF.

  5. Maximum Ind Sets A talk by Bill Gasarch, but based on the literature as described in the AWESOME book: Exact Exponential Algorithms by Fedor Formin and Dieter Kratsch. MISTALK.PDF.

  6. Published paper by Robson that claims to improve MIS algorithms. ROBSON.PDF.

William Gasarch 2013-09-25