Search for dissertations about: "clique number"

Showing result 1 - 5 of 7 swedish dissertations containing the words clique number.

  2. 1. On linear graph invariants related to Ramsey and edge numbers : or how I learned to stop worrying and love the alien invasion

    Author : Oliver Krüger; Jörgen Backelin; Alexander Engström; Stockholms universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Ramsey number; edge number; minimal Ramsey graph; independence number; clique number; Turán s theorem; crochet pattern; H13-pattern; linear graph invariant; triangle-free graph; Mathematics; matematik;

    Abstract : In this thesis we study the Ramsey numbers, R(l,k), the edge numbers, e(l,k;n) and graphs that are related to these. The edge number e(l,k;n) may be defined as the least natural number m for which all graphs on n vertices and less than m edges either contains a complete subgraph of size l or an independent set of size k. READ MORE

  4. 2. Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry

    Author : Mia Persson; Data Vetenskap; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; systems; control; Datalogi; numerical analysis; broadcasting; polygon exploration; robotics; Mathematics; Matematik; Computer science; clique partition; clustering; computational complexity; computational geometry; computational biology; online algorithm; kontroll; approximation algorithm;

    Abstract : The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. READ MORE

  5. 3. On Face Vectors and Resolutions

    Author : Afshin Goodarzi; Anders Björner; Volkmar Welker; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES;

    Abstract : This thesis consist of the following three papers.Convex hull of face vectors of colored complexes. In this paper we verify a conjecture by Kozlov (Discrete ComputGeom18(1997) 421–431), which describes the convex hull of theset of face vectors ofr-colorable complexes onnvertices. READ MORE

  6. 4. Global geometric graph kernels and applications

    Author : Fredrik Johansson; Chalmers tekniska högskola; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES;

    Abstract : This thesis explores the topics of graph kernels and classification of graphs. Graph kernels have received considerable attention in the last decade, in part because of their value in many practical applications, such as chemo informatics and molecular biology, in which classification using graph kernels have become the standard model for several problems. READ MORE

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