Search for dissertations about: "exact satisfiability"

Found 3 swedish dissertations containing the words exact satisfiability.

2. 1. Exact Algorithms for Exact Satisfiability Problems

   Author : Vilhelm Dahllöf; Peter Jonsson; Fedor Fomin; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; NP-hardness; exact algorithms; satisfiability; exact satisfiability; Computer science; Datalogi;

   Abstract : This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. READ MORE

4. 2. Algorithms, measures and upper bounds for satisfiability and related problems

   Author : Magnus Wahlström; Peter Jonsson; Oliver Kullmann; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Exact algorithms; upper bounds; algorithm analysis; satisfiability; Computer science; Datavetenskap;

   Abstract : The topic of exact, exponential-time algorithms for NP-hard problems has received a lot of attention, particularly with the focus of producing algorithms with stronger theoretical guarantees, e.g. upper bounds on the running time on the form O(c^n) for some c. READ MORE

5. 3. Algorithmic Bounds for Presumably Hard Combinatorial Problems

   Author : Andreas Björklund; Institutionen för datavetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; control; Datalogi; numerical analysis; systems; Computer science; Approximation algorithms; Exact algorithms; NP-hard problems; Algorithm theory; kontroll;

   Abstract : In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. READ MORE