Sökning: "exact algorithms"

Visar resultat 1 - 5 av 91 avhandlingar innehållade orden exact algorithms.

  1. 1. Exact Algorithms for Exact Satisfiability Problems

    Författare :Vilhelm Dahllöf; Peter Jonsson; Fedor Fomin; Linköpings universitet; []
    Nyckelord :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. Studies in Efficient Discrete Algorithms

    Författare :DZMITRY SLEDNEU; Matematik (naturvetenskapliga fakulteten); []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Algorithms; Approximation algorithms; Graphs;

    Sammanfattning : This thesis consists of five papers within the design and analysis of efficient algorithms.In the first paper, we consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. We develop a combinatorial randomized algorithm that runs in subcubic time for a special class of graphs. LÄS MER

  4. 3. Exact and approximation algorithms for graph problems with some biological applications

    Författare :Eva-Marta Lundell; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Graph algorithms; computational biology; approximation algorithms; computational complexity; evolutionary trees; maximum agreement subtree; graph embedding; shortest cycle; clique partitioning;

    Sammanfattning : In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them. In particular, we focus on graph algorithms, seeking for the most part polynomial or sub-exponential exact solutions, but in some cases also approximate solutions. LÄS MER

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

    Författare :Magnus Wahlström; Peter Jonsson; Oliver Kullmann; Linköpings universitet; []
    Nyckelord :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

  7. 5. Algorithmic Bounds for Presumably Hard Combinatorial Problems

    Författare :Andreas Björklund; Institutionen för datavetenskap; []
    Nyckelord :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