Sökning: "Vertex Cover"

Visar resultat 1 - 5 av 6 avhandlingar innehållade orden Vertex Cover.

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

    Författare :Aleksa Stankovic; Johan Håstad; Per Austrin; Luca Trevisan; KTH; []
    Nyckelord :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;

    Sammanfattning : 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. LÄS MER

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

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

    Sammanfattning : 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. LÄS MER

  4. 3. Graph dominators in logic synthesis and verification

    Författare :René Krenz; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; formal verification; logic synthesis; dominators; equivalence checking; decomposition; Computer science; Datavetenskap;

    Sammanfattning : 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. LÄS MER

  5. 4. Mathematical Methods for Image Based Localization

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

    Sammanfattning : 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. LÄS MER

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

    Författare :Andrii Dmytryshyn; Bo Kågström; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : 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. LÄS MER