| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 2 / 2
First pagePrevious page1Next pageLast page
1.
Paralelni razveji in omeji algoritem BiqMac Solver
Alen Vegi Kalamar, 2018, master's thesis

Abstract: 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.
Keywords: maksimalen prerez grafa, semidefinitno programiranje, hevristike, algoritem razveji in omeji, paralelno računanje
Published in DKUM: 04.10.2018; Views: 1207; Downloads: 150
.pdf Full text (908,74 KB)

2.
Algoritmični pristopi k problemu maksimalnega prereza grafov
Ksenija Smogavec, 2014, master's thesis

Abstract: Problem maksimalnega prereza grafa je najti takšno razbitje množice vozlišč grafa, da bo vsota uteži na povezavah, ki povezujejo ta dva kosa razbitja, največja. Problem maksimalnega prereza je NP-poln in je eden izmed osnovnih 21-ih Karpovih problemov. Zaradi njegove teoretične in praktične pomembnosti, aplikacije ima v statistični fiziki in vezjih, je bilo zapisanih že kar nekaj različnih aproksimacijskih algoritmov, hevristik ali kombinacij optimizacijskih metod in hevristik, ki rešujejo problem maksimalnega prereza. V magistrskem delu predstavimo problem maksimalnega prereza na posebnih razredih grafov, na katerih lahko najdemo rešitev problema v polinomskem času. Tretje poglavje je namenjeno Goemans Williamsonovemu aproksimacijskemu algoritmu, ki s pomočjo semidefinitnega programa najde rešitev, katere garantirana vrednost je vsaj 87 % optimalne rešitve in predstavlja prelom na področju aproksimacijskih algoritmiov. Poleg njunega algoritma predstavimo še Biq Mac algoritem, ki doseže skoraj optimalne rešitve za grafe z n ≤ 100, in dualno skaliran algoritem, ki je primeren tudi za velike redke grafe. Temu sledi predstavitev posplošitve Goemans Williamsonovega algoritma za maksimalen k-prerez. Nazadnje predstavimo še nekaj hevristik, ki so učinkovite pri iskanju maksimalnega prereza.
Keywords: maksimalen prerez grafa, semidefinitno programiranje, hevristika, NP-poln problem
Published in DKUM: 21.05.2014; Views: 1527; Downloads: 113
.pdf Full text (2,88 MB)

Search done in 0.04 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica