Dominacijske množice na grafihSovdat, Veronika (Avtor) Potočnik, Primož (Mentor) Vidali, Janoš (Komentor) Dominacijska množicanajmanjša dominacijska množicamodeli grafovV 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.20202020-09-17 08:16:02Delo diplomskega seminarja/zaključno seminarsko delo/naloga120203UDK: 519.17VisID: 110555COBISS_ID: 54858243sl