Sökning: "Max-Cut"

Hittade 3 uppsatser innehållade ordet Max-Cut.

  1. 1. Lösning av NP-fullständiga problem genom simulering av dynamiska system

    Kandidat-uppsats, KTH/Skolan för teknikvetenskap (SCI)

    Författare :Jakob Myhrman; Yashar Honarmandi; [2020]
    Nyckelord :;

    Sammanfattning : Många viktiga problem i både vardag och industri tillhör klassen av NP-fullständiga problem, varför det ägnas mycket arbete åt att utveckla heuristiska metoder för att lösa sådana approximativt. Ett exempel är MAX-CUT-problemet, vars lösning är ekvivalent med att hitta grundtillståndet i Isingmodellen. LÄS MER

  3. 2. Improved inapproximability of Max-Cut through Min-Cut

    Master-uppsats, KTH/Skolan för elektroteknik och datavetenskap (EECS)

    Författare :Mårten Wiman; [2018]
    Nyckelord :Inapproximability; Max-Cut; 2-Lin 2 ; NP; Unique games;

    Sammanfattning : A cut is a partition of a graph's nodes into two sets, and we say that an edge crosses the cut if it connects two nodes belonging to different sets. A maximum cut is a cut that maximises the number of crossing edges. LÄS MER

  4. 3. Approximation of Max-Cut on Graphs of Bounded Degree

    Master-uppsats, KTH/Skolan för datavetenskap och kommunikation (CSC)

    Författare :Mikael Florén; [2016]
    Nyckelord :Theoretical Computer Science; Graphs; Algorithms; Max Cut; Approximation; Teoretisk Datalogi; Grafer; Algoritmer; Max Cut; Approximation;

    Sammanfattning : The Max-Cut problem is a well-known NP-hard problem, for which numerous approximation algorithms have been developed over the years. In this thesis, we examine the special case where the degree of vertices in the graph is bounded. LÄS MER