Sökning: "grafer"

Visar resultat 1 - 5 av 24 avhandlingar innehållade ordet grafer.

  1. 1. Local Conditions for Long Cycles in Graphs

    Författare :Jonas B. Granholm; Carl Johan Casselgren; Armen Asratian; Jørgen Bang-Jensen; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle. The problem of determining if a graph is Hamiltonian has been studied extensively, and there are many known sufficient conditions both for Hamiltonicity and for other, related properties. LÄS MER

  3. 2. Efficient Algorithms for Graph-Theoretic and Geometric Problems

    Författare :Peter Floderus; Matematik (naturvetenskapliga fakulteten); []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : This thesis studies several different algorithmic problems in graph theory and in geometry. The applications of the problems studied range from circuit design optimization to fast matrix multiplication. First, we study a graph-theoretical model of the so called ''firefighter problem''. LÄS MER

  4. 3. Performance Monitoring, Analysis, and Real-Time Introspection on Large-Scale Parallel Systems

    Författare :Xavier Aguilar; Erwin Professor; Karl Doctor; Jens Professor; Jesus Labarta; KTH; []
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; HPC; performance analysis; performance monitoring; performance introspection; parallel computing; Computer Science; Datalogi;

    Sammanfattning : High-Performance Computing (HPC) has become an important scientific driver. A wide variety of research ranging for example from drug design to climate modelling is nowadays performed in HPC systems. Furthermore, the tremendous computer power of such HPC systems allows scientists to simulate problems that were unimaginable a few years ago. LÄS MER

  5. 4. Codes on Graphs and More

    Författare :Florian Hug; Institutionen för elektro- och informationsteknik; []
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; convolutional codes; woven graph codes; Low-density parity-check LDPC codes; tailbiting codes; bit error probability; MacWilliams Identity;

    Sammanfattning : Modern communication systems strive to achieve reliable and efficient information transmission and storage with affordable complexity. Hence, efficient low-complexity channel codes providing low probabilities for erroneous receptions are needed. LÄS MER

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

    Författare :Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
    Nyckelord :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;

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