prikaz prve stranice dokumenta Problem maksimalnog težinskog nezavisnog skupa u grafu
  Download
PDF 1.55 MB
master's thesis
Problem maksimalnog težinskog nezavisnog skupa u grafu
Zagreb: University of Zagreb, Faculty of Science, 2023. urn:nbn:hr:217:516468
Brigljević, Juraj
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Brigljević, J. (2023). Problem maksimalnog težinskog nezavisnog skupa u grafu (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević, Juraj. "Problem maksimalnog težinskog nezavisnog skupa u grafu." Master's thesis, University of Zagreb, Faculty of Science, 2023. https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević, Juraj. "Problem maksimalnog težinskog nezavisnog skupa u grafu." Master's thesis, University of Zagreb, Faculty of Science, 2023. https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević, J. (2023). 'Problem maksimalnog težinskog nezavisnog skupa u grafu', Master's thesis, University of Zagreb, Faculty of Science, accessed 23 December 2024, https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević J. Problem maksimalnog težinskog nezavisnog skupa u grafu [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2023 [cited 2024 December 23] Available at: https://urn.nsk.hr/urn:nbn:hr:217:516468

J. Brigljević, "Problem maksimalnog težinskog nezavisnog skupa u grafu", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:217:516468

Metadata
TitleProblem maksimalnog težinskog nezavisnog skupa u grafu
Title (english)The maximum weight independent set problem in a graph
AuthorJuraj Brigljević
MentorRobert Manger (mentor)
Committee memberRobert Manger (predsjednik povjerenstva)
Committee memberGoran Igaly (član povjerenstva)
Committee memberDijana Ilišević (član povjerenstva)
Committee memberZrinka Franušić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2023-09-26, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
Problem maksimalnog težinskog nezavisnog skupa u grafu jedan je NP-težak problem optimizacije. On ima primjene u stvarnome svijetu, koje zahtijevaju brze algoritme koji pronalaze kvalitetna rješenja. Osim toga, u bliskoj je vezi s problemima maksimalne težinske klike i maksimalnog težinskog vršnog pokrivača. U ovome radu definirani su navedeni problemi i iskazane su njihove međusobne veze. Proučena je njihova vremenska složenost u teorijskom smislu i iskazani su relevantni rezultati. Kako je problem maksimalnog težinskog nezavisnog skupa NP-težak, u njegovu rješavanju posežemo za heuristikom kako bismo na brz način pronašli kvalitetna rješenja u općenitom slučaju, a proučavamo i kako se problem može egzaktno riješiti u slučaju stabla. Heuristika koju smo proučili temeljena je na dvjema paradigmama: ponavljanom lokalnom pretraživanju i varijabilnim spustom uz korištenje susjedstava. Ponavljano lokalno pretraživanje heuristika je u kojoj se trudimo pronaći sve bolje rješenje pretraživanjem neke lokalne okoline trenutnoga rješenja. Ideja je da se na taj način trudimo doseći lokalni optimum pod pretpostavkom određene neprekidnosti područja pretraživanja. Kako na taj način možemo zapeti u lokalnom optimumu, u navedeni postupak uključujemo korak perturbacije koji nastoji pronaći ostale lokalne optimume. Da bismo uspjeli efikasno istražiti blizinu trenutnoga rješenja, potreban nam je dobar pojam bliskih rješnja. Iz tog razloga posežemo varijabilnom spustu uz korištenje susjedstava, u kojemu definiramo par susjedstava unutar kojih tražimo bolja rješenja od trenutnoga. Navedeni algoritam je implementiran i testiran na bazama podataka BHOSLIB i DIMACS, na kojima je uočeno da daje kvalitetna rješenja u izrazito malome vremenu.
Abstract (english)
The maximum weight independent set is an NP-hard optimization problem. It has some real-world applications, which require quick algorithms that find quality solutions. Also, it is in a close relationship with the maximum weight clique problem and the maximum weight vertex cover problem. In this thesis, the listed problems are defined and their relationships are expressed and proven. Their time complexity is studied in a theoretical sense and the relevant results are expressed. Since the maximum weight independent set is NP-hard, quality solutions in the general case are found by solving it in a heuristic approach, while the problem is also solved exactly in the case of trees. The studied heuristic is based on two paradigms: iterated local search and variable neighborhood descent. Iterated local search is a heuristic in which we try to find better solutions by searching the local neighborhood of the current solution. The idea is that by doing so we try to reach a local optimum under the assumption of continuity of the search area. Since this can lead to the algorithm getting stuck in a local optimum, a perturbation step is included which attempts to find other local optima. In order to efficiently search the vicinity of the current solution, a good notion of similar solutions is required. For that goal, variable neighborhood descent is defined alongside two notions of neighborhoods which are deemed to contain similar solutions. The algorithm is implemented and tested on the BHOSLIB and DIMACS databases, where it is observed that it quickly finds quality solutions.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:516468
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2024-01-30 12:10:01