Sökning: "Weighted graph"

Visar resultat 1 - 5 av 23 avhandlingar innehållade orden Weighted graph.

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-based Methods for Interactive Image Segmentation

   Författare :Filip Malmberg; Ingela Nyström; Ewert Bengtsson; Jayaram K. Udupa; Uppsala universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Digital image analysis; Interactive image segmentation; Fuzzy image segmentation; Image foresting transform; Graph labeling; Graph cuts; Computerized Image Processing; Datoriserad bildbehandling;

   Sammanfattning : The subject of digital image analysis deals with extracting relevant information from image data, stored in digital form in a computer. A fundamental problem in image analysis is image segmentation, i.e., the identification and separation of relevant objects and structures in an image. LÄS MER

4. 3. Best Trees Extraction and Contextual Grammars for Language Processing

   Författare :Anna Jonsson; Johanna Björklund; Frank Drewes; Hendrik Jan Hoogeboom; Umeå universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Weighted tree automata; the N-best problem; efficient algorithms; semantic graph; abstract meaning representation; contextual graph grammars; hyperedge replacement; graph extensions;

   Sammanfattning : In natural language processing, the syntax of a sentence refers to the words used in the sentence, their grammatical role, and their order. Semantics concerns the concepts represented by the words in the sentence and their relations, i.e., the meaning of the sentence. LÄS MER

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

7. 5. Optimal and Hereditarily Optimal Realizations of Metric Spaces

   Författare :Alice Lesser; Svante Janson; Lars-Erik Persson; Anders Johansson; Vincent Moulton; Pierre Flener; Charles Semple; Uppsala universitet; []
   Nyckelord :Applied mathematics; optimal realization; hereditarily optimal realization; tight span; phylogenetic network; Buneman graph; split decomposition; T-theory; finite metric space; topological graph theory; discrete geometry; Tillämpad matematik;

   Sammanfattning : This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an optimal realization of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique. LÄS MER