Sökning: "NP-Hardness"

Visar resultat 1 - 5 av 7 avhandlingar innehållade ordet NP-Hardness.

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

    Författare :Thomas Petig; Chalmers tekniska högskola; []
    Nyckelord :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;

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

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

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

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

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

  5. 4. Consensus Algorithms for Trees and Strings

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

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

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

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

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