20.500.12556/DKUM-72022 Paralelni razveji in omeji algoritem BiqMac Solver Parallel branch and bound BiqMac Solver Algorithm 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. 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. maksimalen prerez grafa semidefinitno programiranje hevristike algoritem razveji in omeji paralelno računanje max cut semidefinite programming heuristics branch and bound algorithm parallel computation true true false [A. V. Kalamar] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2018-09-06 20:38:02 2018-10-04 15:36:18 2022-08-01 21:52:26 2019-07-11 19:03:24 2018 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.178:004.421(043.2) 24058120 URN:SI:UM:DK:AU08UJQE MAG_Vegi_Kalamar_Alen_2018.pdf MAG_Vegi_Kalamar_Alen_2018.pdf 1 338C602AD68962F3C0520255B5BECE72 22d9c03cf6bc967be5d1437c02262704bcc22b71366da0b5d128472b3663d15c 5de516be-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/4451034a-5bb3-4108-b601-98cac3e1fa96 https://dk.um.si/Dokument.php?lang=slv&id=129953 Fakulteta za naravoslovje in matematiko 0 0 0