Search for dissertations about: "graph partitioning"

Showing result 1 - 5 of 12 swedish dissertations containing the words graph partitioning.

  1. 1. Graph Partitioning and Planted Partitions

    University dissertation from Chalmers University of Technology

    Author : Mikael Onsjö; Chalmers tekniska högskola.; Chalmers University of Technology.; [2008]
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer science; graphs; graph partitioning; graph bisection; clustering; planted partition; algorithms;

    Abstract : Graph partitioning is the problem of splitting a graph into two or more partitions 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 such as VLSI design, parallel processing, bioinformatics, data mining etc. READ MORE

  2. 2. Exact and approximation algorithms for graph problems with some biological applications

    University dissertation from Chalmers University of Technology

    Author : Eva-Marta Lundell; Lunds universitet.; Lund University.; [2009]
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; computational biology; Graph algorithms; approximation algorithms; computational complexity; evolutionary trees; maximum agreement subtree; graph embedding; shortest cycle; clique partitioning;

    Abstract : 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. READ MORE

  3. 3. Constructing Algorithms for Constraint Satisfaction and Related Problems Methods and Applications

    University dissertation from Institutionen för datavetenskap

    Author : Ola Angelsmark; Linköpings universitet.; Linköpings universitet.; [2005]
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; constraint satisfaction; CSP; graph problems; algorithm construction; computational complexity; microstructures; graph colouring; decision problems; optimisation problems; quantum computing; molecular computing; TECHNOLOGY Information technology Computer science; TEKNIKVETENSKAP Informationsteknik Datavetenskap;

    Abstract : In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. READ MORE

  4. 4. Efficient Algorithms for Graph-Theoretic and Geometric Problems

    University dissertation from Centre for Mathematical Sciences, Lund University

    Author : Peter Floderus; Lunds universitet.; Lund University.; [2015]
    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

  5. 5. Gossip-based Algorithms for Information Dissemination and Graph Clustering

    University dissertation from Stockholm : KTH Royal Institute of Technology

    Author : Fatemeh Rahimian; KTH.; RISE.; [2014]
    Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; NATURVETENSKAP; NATURAL SCIENCES;

    Abstract : Decentralized algorithms are becoming ever more prevalent in almost all real-world applications that are either data intensive, computation intensive or both. This thesis presents a few decentralized solutions for large-scale (i) data dissemination, (ii) graph partitioning, and (iii) data disambiguation. READ MORE