Search for dissertations about: "graph problems"

Showing result 11 - 15 of 137 swedish dissertations containing the words graph problems.

  2. 11. Efficient Algorithms for Graph-Theoretic and Geometric Problems

    Author : Peter Floderus; Matematik (naturvetenskapliga fakulteten); []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES;

    Abstract : This thesis studies several different algorithmic problems in graph theory and in geometry. The applications of the problems studied range from circuit design optimization to fast matrix multiplication. First, we study a graph-theoretical model of the so called ''firefighter problem''. READ MORE

  4. 12. Optimal input design for nonlinear dynamical systems : a graph-theory approach

    Author : Patricio E. Valenzuela Pacheco; Cristian R. Rojas; Roland Hildebrand; KTH; []
    Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Input design; Markov chains; system identification; Electrical Engineering; Elektro- och systemteknik;

    Abstract : Optimal input design concerns the design of an input sequence to maximize the information retrieved from an experiment. The design of the input sequence is performed by optimizing a cost function related to the intended model application. Several approaches to input design have been proposed, with results mainly on linear models. READ MORE

  5. 13. Random geometric graphs and their applications in neuronal modelling

    Author : Fioralba Ajazi; Matematisk statistik; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; random graph; Neural Network; Probability; Inhomogeneous random graph; random distance graph; random grown networks;

    Abstract : Random graph theory is an important tool to study different problems arising from real world.In this thesis we study how to model connections between neurons (nodes) and synaptic connections (edges) in the brain using inhomogeneous random distance graph models. READ MORE

  6. 14. On random satisfiability and optimization problems

    Author : Joel Larsson; Klas Markström; Roland Häggkvist; Victor Falgas Ravry; Stefanie Gerke; Umeå universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Random graphs; k-SAT; satisfiability; coupon collector; random cover time; threshold phenomenon; concentration of measure; combinatorial probability; perfect matching; assignment problem; local graph limit; mean-field; Mathematics; matematik;

    Abstract : In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. READ MORE

  7. 15. Algorithmic Bounds for Presumably Hard Combinatorial Problems

    Author : Andreas Björklund; Institutionen för datavetenskap; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; control; Datalogi; numerical analysis; systems; Computer science; Approximation algorithms; Exact algorithms; NP-hard problems; Algorithm theory; kontroll;

    Abstract : In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. READ MORE