Exact Algorithms for Variants of Satisfiability and Colouring Problems
Bjarke Skjernaa November 2004 |
Abstract:
This dissertation studies exact algorithms for various hard
problems and give an overview of not only results but also the techniques
used.
In the first part we focus on Satisfiability and several
variants of Satisfiability. We present some historical techniques and
results. Our main focus in the first part is on a particular variant of
Satisfiability, Exact Satisfiability. Exact Satisfiability is the variant of
Satisfiability where a clause is satisfied if it contains exactly one true
literal. We present an algorithm solving Exact Satisfiability in time
We present a new program which generates algorithms and corresponding upper bound proofs for variants of Satisfiability, and in particular Exact Satisfiability. The program uses several new techniques which we describe and compare to the techniques used in three other programs generating algorithms and upper bound proofs.
In the second part we focus on another class of NP-complete problems,
colouring problems. We present several algorithms for 3-Colouring, and
discuss
In
the last part of this dissertation we look at a class of problems unrelated
to the above, Graph Distinguishability problems. DIST Available as PostScript, PDF. |