prikaz prve stranice dokumenta Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima
Rad nije dostupan
diplomski rad
Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2022. urn:nbn:hr:168:624118
Domislović, Jakob
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Domislović, J. (2022). Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:624118

Domislović, Jakob. "Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2022. https://urn.nsk.hr/urn:nbn:hr:168:624118

Domislović, Jakob. "Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2022. https://urn.nsk.hr/urn:nbn:hr:168:624118

Domislović, J. (2022). 'Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima', Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 24.11.2024., https://urn.nsk.hr/urn:nbn:hr:168:624118

Domislović J. Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2022 [pristupljeno 24.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:624118

J. Domislović, "Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima", Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2022. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:624118

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:624118
Podaci o radu
NaslovOdređivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima
Naslov (engleski)Determination of the minimal independent dominating set in general graphs
AutorJakob Domislović
MentorStjepan Bogdan (mentor)
Član povjerenstvaStjepan Bogdan (član povjerenstva)
Član povjerenstvaTamara Petrović (član povjerenstva)
Član povjerenstvaGoran Vasiljević (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
Zagreb
Datum i država obrane2022-07-11, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Elektrotehnika
Sažetak
Pronalaženje minimalnog nezavisnog dominantnog seta (MIDS) je NP težak kombinatorni optimizacijski problem. Budući da se stvari u svijetu često mogu modelirati kao grafovi, MIDS ima široku primjenu u različitim granama. S obzirom na težinu pronalaženja MIDS-a obično se njegovom rješavanju pristupa heuristički i metaheuristički. U ovom radu predloženo je rješenje pomoću genetskog algoritma s lokalnim pretraživanjem temeljenog na diskretnom gradijentnom spustu i popravljanjem nemogućih rješenja. Također, dano je aproksimativno rješenje u kojem se čvorovi grafa prije pretraživanja grupiraju pomoću spektralnog grupiranja. Na posljetku su prikazani rezultati pronalaženja MIDS-a s na DIMACS grafovima. Ispostavlja se da su u većini slučajeva rješenja nezavisna i dominantna, no ne uvijek i minimalna. Aproksimativnim pristupom se brže dolazi do rješenja, no ne garantira se minimalnost ni nezavisnot.
Sažetak (engleski)
The search for the minimal independent dominating set (MIDS) is an NP-hard combinatorial optimization problem. Since things in the world can often be modeled as graphs, MIDS has wide application in a variety of industries. Given the difficulty of finding MIDS, its solution is usually approached heuristically and metaheuristically. In this thesis, a solution is proposed using the genetic algorithm with local search based on discrete gradient descent and repair of infeasible solutions. In addition, an approximate solution is given where the nodes of the graph are clustered using spectral clustering before the search. Finally, the results of the MIDS on DIMACS graphs are presented. It is shown that the solutions are independent and dominant in most cases, but not always minimal. An approximate approach leads to a faster solution, but does not guarantee minimalism or independence.
Ključne riječi
Ključne riječi (engleski)
Jezikengleski
URN:NBNurn:nbn:hr:168:624118
Studijski programNaziv: Elektrotehnika i informacijska tehnologija
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (mag. ing. el. techn. inf.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2023-01-14 08:41:14