Sökning: "minimum spanning tree"

Visar resultat 1 - 5 av 11 avhandlingar innehållade orden minimum spanning tree.

  1. 1. Progress in Hierarchical Clustering & Minimum Weight Triangulation

    Författare :Drago Krznaric; Institutionen för datavetenskap; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; computer technology; Systems engineering; minimum spanning tree; complete linkage; hierarchical clustering; minimum weight triangulation; greedy triangulation; Data- och systemvetenskap;

    Sammanfattning : In this thesis we study efficient computational methods for geometrical problems of practical importance and theoretical interest. The problems that we consider are primarily complete linkage clustering, minimum spanning trees, and approximating minimum weight triangulation. Below is a list of the main results proved in the thesis. LÄS MER

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

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

  5. 4. Dynamic algorithms: new worst-case and instance-optimal bounds via new connections

    Författare :Thatchaphol Saranurak; Danupon Nanongkai; Piotr Sankowski; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computer Science; Datalogi;

    Sammanfattning : This thesis studies a series of questions about dynamic algorithms which are algorithms for quickly maintaining some information of an input data undergoing a sequence of updates. The first question asks \emph{how small the update time for handling each update can be} for each dynamic problem. LÄS MER

  7. 5. Data Mining Approaches for Outlier Detection Analysis

    Författare :Shahrooz Abghari; Niklas Lavesson; Håkan Grahn; Veselka Boeva; Olga Fink; Blekinge Tekniska Högskola; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; outlier detection; data modelling; machine learning; clustering analysis; data stream mining; Computer Science; Datavetenskap;

    Sammanfattning : Outlier detection is studied and applied in many domains. Outliers arise due to different reasons such as fraudulent activities, structural defects, health problems, and mechanical issues. The detection of outliers is a challenging task that can reveal system faults, fraud, and save people's lives. LÄS MER