2007
Algorithms, measures, and upper bounds for satisfiability and related problems, PhD Thesis (Linköping Studies in Science and Technology, PhD Dissertation no 1079). Available online through
Linköping University e-press, or here as a
PDF or
Postscript file.
The thesis is a monograph, and in addition to new presentations of old results,
it contains the following otherwise unpublished new results:
- A new O(1.0984^n) time exact algorithm for Exact 3-satisfiability (X3SAT) in chapter 5.
- A new exact algorithm for 3-hitting set (3HS), also known as the minimum transversal problem for rank 3 hypergraphs, with a running time in
O(p(n)*2.0755^k) with a limit k on the size of the hitting set, using polynomial space,
and an exponential space speedup achieving a non-parameterized running time in O(1.6278^n), are in chapter 6.
(A classical bound of O(1.6359^n) time with polynomial space is also
given, but there is a problem in the proof of Lemma 58 which casts some
doubt on it.)
- An algorithm for counting weighted solutions to 2SAT forumals (#2SAT), in O(1.2377^n) time, in chapter 7. (Now accepted at IWPEC 2008.)
- A small tightening of the analysis for the #3SAT algorithm of our TCS paper, now giving bound O(1.6671^n), is in chapter 8.
