Sökning: "Graph algorithms"

Visar resultat 1 - 5 av 121 avhandlingar innehållade orden Graph algorithms.

1. 1. Order-preserving graph grammars

   Författare :Petter Ericson; Henrik Björklund; Frank Drewes; Sebastian Maneth; Umeå universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Graph grammars; graph parsing; graph series; hyperedge replacement; uniform parsing problem; abstract meaning representation; semantic modelling; order preservation; reentrancy preservation; minimally adequate teacher; weighted graph grammars;

   Sammanfattning : The field of semantic modelling concerns formal models for semantics, that is, formal structures for the computational and algorithmic processing of meaning. This thesis concerns formal graph languages motivated by this field. LÄS MER

3. 2. Graph Partitioning and Planted Partitions

   Författare :Mikael Onsjö; Chalmers tekniska högskola; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; planted partition; graph bisection; algorithms; graphs; graph partitioning; clustering;

   Sammanfattning : Graph partitioning is the problem of splitting a graph into two or morepartitions of fixed sizes while minimizing the number of edges that are “cut”.This is an important problem with a wide range of applications in fields suchas VLSI design, parallel processing, bioinformatics, data mining etc. 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. 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

7. 5. Algorithmic Graph Problems - From Computer Networks to Graph Embeddings

   Författare :Martin Wahlén; Data Vetenskap; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Approximation Algorithms; Exact Algorithms; Time Complexity; Broadcasting;

   Sammanfattning : This dissertation is a contribution to the knowledge of the computational complexity of discrete combinatorial problems. 1. The first problem that we consider is to compute the maximum independent set of a box graph, that is, given a set of orthogonal boxes in the plane compute the largest subset such that no boxes in the subset overlap. LÄS MER