| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Paralelni razveji in omeji algoritem BiqMac Solver
Avtorji:ID Vegi Kalamar, Alen (Avtor)
ID Bokal, Drago (Mentor) Več o mentorju... Novo okno
ID Povh, Janez (Komentor)
Datoteke:.pdf MAG_Vegi_Kalamar_Alen_2018.pdf (908,74 KB)
MD5: 338C602AD68962F3C0520255B5BECE72
PID: 20.500.12556/dkum/4451034a-5bb3-4108-b601-98cac3e1fa96
 
Jezik:Slovenski jezik
Vrsta gradiva:Magistrsko delo/naloga (mb22)
Tipologija:2.09 - Magistrsko delo
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis:Problem maksimalnega prereza je primer NP težkega problema. To pomeni, da ne poznamo učinkovitega polinomskega algoritma za reševanje problema za poljuben graf in domnevamo, da tudi ne obstaja. Kljub temu obstajajo pristopi, kako reševati problem do optimalnosti. V kolikor poznamo učinkovite hevristike in poenostavitve problema, je primeren pristop algoritem razveji in omeji. Rendl, Rinaldi in Wiegele so z uporabo različnih poenostavitev, dualne teorije, aproksimacijskih algoritmov in hevristik razvili učinkovit algoritem razveji in omeji z imenom BiqMac Solver, ki optimalno reši problem maksimalnega prereza tudi za večje grafe. Zaradi strukture je algoritem primeren, da ga implementiramo za paralelno izvajanje. Namen magistrskega dela je predstavitev algoritma BiqMac in njegova paralelna implementacija.
Ključne besede:maksimalen prerez grafa, semidefinitno programiranje, hevristike, algoritem razveji in omeji, paralelno računanje
Leto izida:2018
Založnik:[A. V. Kalamar]
Izvor:Maribor
PID:20.500.12556/DKUM-72022 Novo okno
UDK:519.178:004.421(043.2)
COBISS.SI-ID:24058120 Novo okno
NUK URN:URN:SI:UM:DK:AU08UJQE
Datum objave v DKUM:04.10.2018
Število ogledov:1210
Število prenosov:150
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:FNM
:
Kopiraj citat
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Licence

Licenca:CC BY-SA 4.0, Creative Commons Priznanje avtorstva-Deljenje pod enakimi pogoji 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-sa/4.0/deed.sl
Opis:Ta licenca Creative Commons je zelo podobna običajni licenci Priznanje avtorstva, vendar zahteva, da so materialne avtorske pravice na izpeljanih delih upravljane z enako licenco.
Začetek licenciranja:06.09.2018

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Parallel branch and bound BiqMac Solver Algorithm
Opis:The max cut problem is a NP hard problem. That means that no effective algorithm for this problem is known, and it is conjectured that none exists. However, there are a few possible methods of optimally solving these problems. If the efficient heuristics and relaxations of the problem are known, a correct procedure is using a branch and bound algorithm. Using various relaxations, duality theory, approximation algorithms and heuristics, Rendl, Rinaldi and Wiegele developed an effective branch and bound algorithm called BiqMac Solver, which optimally solves max cut problems, even for large graphs. Because of its structure, the algorithm is appropriate for parallel computing. The purpose of this master’s thesis is to present the BiqMac algorithm and its parallel implementation.
Ključne besede:max cut, semidefinite programming, heuristics, branch and bound algorithm, parallel computation


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici