izpis_h1_title_alt

Dominacijske množice na grafih : delo diplomskega seminarja
Sovdat, Veronika (Author), Potočnik, Primož (Mentor) More about this mentor... This link opens in a new window, Vidali, Janoš (Co-mentor)

.pdfPDF - Presentation file, Download (1,26 MB)
MD5: 0F601F1683AA0F80A68ABBE28BDBF783

Abstract
V diplomski nalogi obravnavam dominacijske množice na grafih. Raziskala sem različne algoritme za iskanje najmanjše dominacijske množice in njenih približkov. Algoritme sem preizkusila na različnih modelih grafov. Raziskala sem natančnost približnih metod za različne modele grafov in časovne zahtevnosti algoritmov za vsak model grafov posebej. S simulacijami sem potrdila oceno za natančnost požrešne metode, ki sem jo predhodno teoretično dokazala. Ocena je zelo dobra za model Erdős–Rényijevih grafov. Velja tudi za Barabási–Albertov model, čeprev bi se za slednji model dalo dobiti tudi nižjo zgornjo mejo.

Language:Slovenian
Keywords:Dominacijska množica, najmanjša dominacijska množica, modeli grafov
Work type:Bachelor thesis/paper (mb11)
Organization:FMF - Faculty of Mathematics and Physics
Year:2020
UDC:519.17
COBISS.SI-ID:54858243 This link opens in a new window
Views:248
Downloads:65
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:English
Title:Dominating sets in graphs
Abstract:
In my dissertation, I focus on the dominating set in graphs. I have researched different algorithms to find the minimum dominating sets and their approximations. I have tested the algorithms on different graph models. I have investigated the accuracy of various methods on various models of graphs and their time complexities. With the simulations, I have confirmed the estimate for the accuracy of the greedy method, which I had previously proved theoretically. The estimate is very good for the Erdős--Rényi graph model. It also applies to the Barabási--Albert model, although a lower upper bound could be obtained for this kind of graphs.

Keywords:Dominating set, minimum dominating set, graph models

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back