| Naslov: | Paralelni razveji in omeji algoritem BiqMac Solver |
|---|
| Avtorji: | ID Vegi Kalamar, Alen (Avtor)
ID Bokal, Drago (Mentor) Več o mentorju... 
ID Povh, Janez (Komentor) |
|---|
| Datoteke: |  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 |
|---|
| 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 |
|---|
| Kraj izida: | Maribor |
|---|
| Založnik: | [A. V. Kalamar] |
|---|
| Leto izida: | 2018 |
|---|
| PID: | 20.500.12556/DKUM-72022 |
|---|
| UDK: | 519.178:004.421(043.2) |
|---|
| COBISS.SI-ID: | 24058120 |
|---|
| NUK URN: | URN:SI:UM:DK:AU08UJQE |
|---|
| Datum objave v DKUM: | 04.10.2018 |
|---|
| Število ogledov: | 2095 |
|---|
| Število prenosov: | 252 |
|---|
| Metapodatki: |    |
|---|
| Področja: | FNM
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
