Search for dissertations about: "maximum clique"

Found 5 swedish dissertations containing the words maximum clique.

  2. 1. Classification and nonexistence results for binary linear codes

    Author : Erik Lorentzen; Göteborgs universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Algorithms; classification of codes; linear codes; maximum clique; optimal codes; linear codes;

    Abstract : .... READ MORE

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

    Author : Eva-Marta Lundell; Data Vetenskap; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Graph algorithms; computational biology; 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

  5. 3. Lower Bounds and Trade-offs in Proof Complexity

    Author : Susanna F. de Rezende; Jakob Nordström; Amit Chakrabarti; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Proof complexity; trade-offs; lower bounds; size; length; space; Computer Science; Datalogi;

    Abstract : Propositional proof complexity is a field in theoretical computer science that analyses the resources needed to prove statements. In this thesis, we are concerned about the length of proofs and trade-offs between different resources, such as length and space. READ MORE

  6. 4. Algorithmic Graph Problems - From Computer Networks to Graph Embeddings

    Author : Martin Wahlén; Data Vetenskap; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Approximation Algorithms; Exact Algorithms; Time Complexity; Broadcasting;

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

  7. 5. On Statistical Modeling of Social Networks

    Author : Ingegärd Jansson; Charles Kaplan; Stockholms universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Statistics; Statistik; statistik; Statistics;

    Abstract : A social network is formed by a collection of individuals and the contacts or relations between them. The focus is here on relations defined by sociometric choices, implying that the individuals in the network have been required to choose among the other individuals in the group according to some criteria. READ MORE