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

master's thesis

• Title (english): Determination of the minimal independent dominating set in general graphs
• Author: Jakob Domislović
• Mentor: Stjepan Bogdan (mentor)
• Committee member: Stjepan Bogdan (član povjerenstva)
• Committee member: Tamara Petrović (član povjerenstva)
• Committee member: Goran Vasiljević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

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.

Abstract (english)

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.

• Keywords: teorija grafova; minimalni nezavisni dominantni skup; optimizacija; genetski algoritam; heuristika; metaheuristika; grupiranje
• Keywords (english): Graph Theory; Minimal Independent Dominating Set; Optimization; Genetic Algorithm; Heuristic; Metaheuristic; Clustering
• Language: english
• URN:NBN: urn:nbn:hr:168:624118
• Study programme: Title: Electrical Engineering and Information Technology; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 08:41:14