Sökning: "Fixed-Parameter Algorithm"

Hittade 5 avhandlingar innehållade orden Fixed-Parameter Algorithm.

  1. 1. Fixed-Parameter Algorithms for Optimal Convex Partitions and Other Results

    Författare :Magdalene Grantson Borgelt; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; control; Datalogi; numerical analysis; Convex Partition; Computer science; Triangulation; kontroll; system; numerisk analys; systems; Fixed-Parameter Algorithm; Spanning Tree;

    Sammanfattning : In this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. LÄS MER

  3. 2. Fixed parameter algorithms and other results for convex patitions

    Författare :Magdalene Grantson Borgelt; Data Vetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NP-hard. Partitioning polygons with holes into the minimum number of convex polygons MNCP is also known to be NP-hard. LÄS MER

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

  5. 4. Combinatorial Slice Theory

    Författare :Mateus de Oliveira Oliveira; Karl Meinke; Stefan Arnborg; Barbara König; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Combinatorial Slice Theory; Partial Order Theory of Concurrency; Digraph Width Measures; Equational Logic;

    Sammanfattning : Slices are digraphs that can be composed together to form larger digraphs.In this thesis we introduce the foundations of a theory whose aim is to provide ways of defining and manipulating infinite families of combinatorial objects such as graphs, partial orders, logical equations etc. LÄS MER

  7. 5. 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