20.500.12556/RUL-120203 Dominacijske množice na grafih delo diplomskega seminarja Dominating sets in graphs 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. 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. Dominacijska množica najmanjša dominacijska množica modeli grafov Dominating set minimum dominating set graph models true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2020-09-17 08:16:02 2020-09-17 08:16:05 2024-05-29 14:28:06 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 110555 54858243 1439.pdf 1439.pdf 1 0F601F1683AA0F80A68ABBE28BDBF783 92d7dc59eb5e4b35ec5ac34b555bb93240ae9f6490754a8b57ad60ed24b03e8d 068d70be-a1ba-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=134982 Fakulteta za matematiko in fiziko 0 0 0