Search for dissertations about: "hypergraph"

Showing result 1 - 5 of 11 swedish dissertations containing the word hypergraph.

  2. 1. On hypergraph algebras

    Author : Eric Emtander; Jörgen Backelin; Ralf Fröberg; Jakob Jonsson; Stockholms universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Mathematics; matematik;

    Abstract : .... READ MORE

  4. 2. Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness

    Author : Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Combinatorial optimization; approximation; inapproximability; hardness; probabilistically checkable proofs; pcp; perfect completeness; boolean constraint satisfaction problem; csp; graph coloring; hypergraph coloring; direct sum; superposition; label cover; Computer Science; Datalogi;

    Abstract : A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. READ MORE

  5. 3. Parameterized algorithms for hitting set variants applied to protein identification in shotgun proteomics

    Author : Leonid Molokov; Chalmers tekniska högskola; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Union Editing; Fixed Parameter Tractable; Shotgun proteomics; Hitting Set; Parameterized complexity; Hypergraph; Set Cover;

    Abstract : This work is dedicated to problem of protein identification in bottom-up proteomics, and in particular, in shotgun proteomics. It is aimed on providing a new way of interpretation of peak lists. READ MORE

  6. 4. Protein Mixture Inference as Hitting Set Variants and Linear Algebra Problems

    Author : Leonid Molokov; Chalmers tekniska högskola; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Union Editing; Shotgun proteomics; Parameterized complexity; Protein Inference; Shared Peptides; Set Cover; Hypergraph; Hitting Set; Fixed Parameter Tractable; Protein Quan- ti; Star Editing;

    Abstract : This work is dedicated to the problems of protein inference and quantification in bottom-up proteomics, and, in particular, in shotgun proteomics. We adopt a rather classical approach of representing inference problem as a set cover, where proteins are understood as sets of their observations: peptides' masses or sequences. READ MORE

  7. 5. Chordal and Complete Structures in Combinatorics and Commutative Algebra

    Author : Eric Emtander; Jörgen Backelin; Ralf Fröberg; Bernd Sturmfels; Stockholms universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Betti numbers; chordal hypergraphs; complete hypergraphs; hypercycle; line hypergraph; numerical monoids; positive affine monoids; Other mathematics; Övrig matematik; Mathematics; matematik;

    Abstract : This thesis is divided into two parts. The first part is concerned with the commutative algebra of certain combinatorial structures arising from uniform hypergraphs. The main focus lies on two particular classes of hypergraphs called chordal hypergraphs and complete hypergraphs, respectively. READ MORE