Određivanje minimalnog nezavisnog dominantnog skupa u općenitim grafovima

diplomski rad

• Naslov (engleski): Determination of the minimal independent dominating set in general graphs
• Autor: Jakob Domislović
• Mentor: Stjepan Bogdan (mentor)
• Član povjerenstva: Stjepan Bogdan (član povjerenstva)
• Član povjerenstva: Tamara Petrović (član povjerenstva)
• Član povjerenstva: Goran 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 obrane: 2022-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: teorija grafova; minimalni nezavisni dominantni skup; optimizacija; genetski algoritam; heuristika; metaheuristika; grupiranje
• Ključne riječi (engleski): Graph Theory; Minimal Independent Dominating Set; Optimization; Genetic Algorithm; Heuristic; Metaheuristic; Clustering
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:624118
• Studijski program: Naziv: 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 resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 08:41:14