Sökning: "exact satisfiability"

Hittade 3 avhandlingar innehållade orden exact satisfiability.

  1. 1. Exact Algorithms for Exact Satisfiability Problems

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

    Sammanfattning : 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. LÄS MER

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

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

    Sammanfattning : 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. LÄS MER

  4. 3. Algorithmic Bounds for Presumably Hard Combinatorial Problems

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

    Sammanfattning : 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. LÄS MER