Search for dissertations about: "vertex cover"

Showing result 1 - 5 of 6 swedish dissertations containing the words vertex cover.

  2. 1. Hardness of Approximating Constraint Satisfaction Problems and Their Variants in Presence of Additional Structural Assumptions

    Author : Aleksa Stankovic; Johan Håstad; Per Austrin; Luca Trevisan; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Hardness of Approximation; Approximation Algorithms; Label Cover; Vertex Cover; Unique Games Conjecture; Max-3-Lin; Universal Factor Graphs; Regular Constraint Satisfaction Problems; Inapproximerbarhet; Approximationsalgoritm; Label Cover; Vertex Cover; Unique Games Conjecture; Max-3-Lin; Universell Faktorgraf; Regelbundna Begränsningsproblem; Datalogi; Computer Science;

    Abstract : This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfaction problems (CSPs), which are considered to be one of the most fundamental problems in theoretical computer science. READ MORE

  4. 2. A Finite Element Model of the Human Head for Simulation of Bone-conducted Sound

    Author : You Chang; Stefan Stenfelt; Namkeun Kim; Frank Böhnke; Linköpings universitet; []
    Keywords : MEDICIN OCH HÄLSOVETENSKAP; MEDICAL AND HEALTH SCIENCES; bone conduction; finite element model，bone-conduction devices;

    Abstract : Bone conduction is usually understood as the hearing sensation based on the vibrations of the skull bone and surrounding tissues. The fact that vibration of the skull bones can result in a sound percept has been known for a long time. However, it is difficult to give a general definition of BC sound. READ MORE

  5. 3. Graph dominators in logic synthesis and verification

    Author : René Krenz; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; formal verification; logic synthesis; dominators; equivalence checking; decomposition; Computer science; Datavetenskap;

    Abstract : This work focuses on the usage of dominators in circuit graphs in order to reduce the complexity of synthesis and verification tasks. One of the contributions of this thesis is a new algorithm for computing multiple-vertex dominators in circuit graphs. READ MORE

  6. 4. Mathematical Methods for Image Based Localization

    Author : Klas Josephson; Matematik LTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Multiple View Geometry; Image Based Localization; Computer Vision; Gröbner Basis; Minimal Problems;

    Abstract : The underlying question in localization is, where am I? In this thesis a purely image based approach is proposed to solve this problem. In order to create a complete image based system, there are many subproblems that have to be addressed. The localization problem can also be solved in other ways, for example, with a GPS. READ MORE

  7. 5. Skew-symmetric matrix pencils : stratification theory and tools

    Author : Andrii Dmytryshyn; Bo Kågström; Umeå universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES;

    Abstract : Investigating the properties, explaining, and predicting the behaviour of a physical system described by a system (matrix) pencil often require the understanding of how canonical structure information of the system pencil may change, e.g., how eigenvalues coalesce or split apart, due to perturbations in the matrix pencil elements. READ MORE