Search for dissertations about: "NP-hardness"

Showing result 1 - 5 of 7 swedish dissertations containing the word NP-hardness.

  2. 1. Topics in Distributed Algorithms: On Wireless Networks, Distributed Storage and Streaming

    Author : Thomas Petig; Chalmers tekniska högskola; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Message Passing; Wireless Networks; Time Division Multiple Access; Shared Memory; Fault-Tolerance; Streaming; NP-Hardness; Distributed Algorithm; Optimisation; TDMA;

    Abstract : Distributed algorithms are executed on a set of computational instances. Werefer to these instances as nodes. Nodes are runningconcurrently and are independent from each other. Furthermore, they have their own instructions and information. READ MORE

  4. 2. 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

  5. 3. Parameterized algorithms for hitting set variants applied to protein identification in shotgun proteomics

    Author : Leonid Molokov; Chalmers tekniska högskola; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Union Editing; Fixed Parameter Tractable; Shotgun proteomics; Hitting Set; Parameterized complexity; Hypergraph; Set Cover;

    Abstract : This work is dedicated to problem of protein identification in bottom-up proteomics, and in particular, in shotgun proteomics. It is aimed on providing a new way of interpretation of peak lists. READ MORE

  6. 4. Consensus Algorithms for Trees and Strings

    Author : Jesper Jansson; Institutionen för datavetenskap; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerical analysis; computational complexity; Approximation algorithm; labeled tree; lowest common ancestor constraint; maximum agreement subtree; alignment between trees; clustering; Computer science; Hamming metric; systems; control; Datalogi; numerisk analys; system; kontroll;

    Abstract : This thesis studies the computational complexity and polynomial-time approximability of a number of discrete combinatorial optimization problems involving labeled trees and strings. The problems considered have applications to computational molecular biology, pattern matching, and many other areas of computer science. READ MORE

  7. 5. Computational problems in evolution : Multiple alignment, genome rearrangements, and tree reconstruction

    Author : Isaac Elias; Jens Lagergren; Lior Pachter; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Distance Methods; Tree reconstruction; Sorting by Transpositions; multiple alignment; ancestral sequences; Computer science; Datavetenskap;

    Abstract : Reconstructing the evolutionary history of a set of species is a fundamental problem in biology. This thesis concerns computational problems that arise in different settings and stages of phylogenetic tree reconstruction, but also in other contexts. READ MORE